关于数据结构 堆排序
发布网友
发布时间：2022-04-22 10:53
共1个回答
热心网友
时间：2022-04-26 13:23
***建堆可以用自底向上的方法将一个大小为n=A.length的数组A[1...N]转换为最大堆。
BuildMaxHeap（A）
1. A.HeapSize=A.length
2. for i=A.length/2 downto 1
3. MaxHeapify(A,i) //该函通过让A[i]的值在最大堆中‘逐级下降’，从而使得下标为i的根节点的 //子树重新最大堆性质遵循
MaxHeapify(A,i)
1.l=Left(i)
2.r=Right(i)
3.if l<=A.HeapSize and A[l]>A[i]
4. largest=l
5. else largest=i
6.if r<=A.HeapSize and A[r]>A[largest]
7. largest=r
8.if largest!=i
9. exchangeA[i] with A[largest]
10. MaxHeapify(A,largest)
在建堆中，初始化：在第一次迭代钱，i=n/2,而n/2+1，n/2+2...都为叶节点，因而是平凡最大堆的根节点。
保持：因为每次迭代都维护该循环不变量，切该i的孩子的节点均比i大。所以它们都是最大堆的根节点。
终止：终止时i=0，每个节点1，2..n都是最大堆的根，而1为堆的根。
堆排序
通过buildMH来创建堆，因为最大元素总在根节点A[l],通过与A[n]进行互换从而达到正确位置。实质上就是不断调用上面的MaxHeapify(A,i)从而在A[1...n-1]上构造一个新的最大堆。直到堆的大小从n-1降到2。
HeapSort(A)
1.BuildMaxHeap(A)
2.for i=A.length downto 2
3. exchange A[l] with A[i]
4. A.HeapSize=A.HearSize-1
5. MaxHeapify(A,l)
