堆-顧名思義，上面小，下面大，或者上面大，下面小。

在堆排序過程中，首先應該建堆。如何將數組中的元素建立成一個規范的堆行結構。

二叉堆是完全二叉樹或者是近似完全二叉樹。二叉堆滿足二個特性：

1．父結點的鍵值總是大于或等于（小于或等于）任何一個子節點的鍵值。

2．每個結點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。

當父結點的鍵值總是大于或等于任何一個子節點的鍵值時為最大堆。當父結點的鍵值總是小于或等于任何一個子節點的鍵值時為最小堆。

假設根結點的下標為1，則第 i 個結點的父結點下標為 i / 2 ， 第 i 個結點的左子結點的下標為2*i, 右子結點的下標為2*i+1 ;

如何才能使得數組中元素形成堆的結構呢？首先將父結點、左子結點、右子結點這三個結點看成一個小堆或者一個小三角形，葉子結點無左子結點和右子結點，所以默認葉子結點為堆結構。則最后一個元素的父結點下標為 i/2， 從 i/2 開始，直到根結點為止，小三角形的面積逐漸增大，到根結點時達到最大，也就完成了堆的建立。

接下來進行的是堆排序操作，由于根結點元素為最大元素，每次先將根結點元素和最后一個元素調換，然后再調整堆即可，直到堆中元素只剩一個時結束，這樣數組中的元素就為有序的元素。具體代碼如下：

#include<stdio.h>void MaxHeap(int a[] , int i , int n) {int j ;a[0] = a[i] ;j = 2 * i ;while ( j <= n ) {if(j + 1 <= n && a[j + 1] > a[j])j++ ;if(a[0] >= a[j])break ;a[i] = a[j] ;i = j ;j = 2 * i ;}a[i] = a[0] ; }void MakeMaxheap(int a[] , int n ) {int i ;for(i = n / 2 ; i >= 1 ; i--)MaxHeap(a,i,n) ; } void swap(int &a , int &b) {int t = a ;a = b ;b = t ; } void Delete(int a[] , int n ) {swap(a[1],a[n]) ; // printf("%d\n",a[1]) ;MaxHeap(a,1,n-1) ; } int main() {int a[] = {0,16,4,10,14,7,9,3,2,8,1} ;MakeMaxheap(a,10) ;int i ;for(i = 1 ; i < 11 ; i++)printf("%d ",a[i]) ;printf("\n") ;return 0 ; }

轉載于:https://www.cnblogs.com/NYNU-ACM/p/4237401.html

總結

以上是生活随笔為你收集整理的堆排序的进一步理解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。