首页 > 代码库 > [数据结构学习备忘录]堆及其堆排序

[数据结构学习备忘录]堆及其堆排序

[数据结构学习备忘录]

一种数据结构,物理存储方式:数组

                       逻辑存储方式:近似于完全二叉树,假定i为堆元素的序数[Index],那么i/2就是该元素的左子树,(i/2 + 1)就是该元素的右子树,分为两种堆:大根堆、小根堆;这两种堆的区别是:大根堆的根节点元素的值比左右子树的值都要大,小根堆则相反。

可用这种数据结构进行排序,称为堆排序。

 

与该数据结构相关的关键算法:

①   MaxHeaplfy 当堆的元素顺序出现错误时的调整函数

②   BulidMax[min]Heap 建立大[小]根堆

③   HeapSort 堆排序

此外插入算法每次将元素插入堆的最后一位,然后用算法1进行顺序的调整,删除元素时则将堆的最后一位补上,用算法1进行顺序的调整。

 

 未完...

[数据结构学习备忘录]堆及其堆排序