堆（二叉堆）作為一種比較重要的資料結構，完全二叉樹的線性存儲。其典型的應用就是堆排序和優先隊列。
堆（Heap）
堆（二叉堆）是一個數組，也可以被看做一個近似的完全二叉樹。将二叉樹從頂層向底層，從左向右，從1開始編号，直到二叉樹節點個數n。得到完全二叉樹的層序周遊序列，即是二叉堆。
二叉堆中編号是從1到n的，是以節點 i 的父節點編号為 ⌊ i/2⌋ ⌊ i / 2 ⌋ （i/2向下取整，在進階語言中，整型運算i/2即可做到），左孩子為2i，右孩子為2i+1。
即有：
Parent(i)
return i/
Left(i)
return *i
Right(i)
return *i+
在實際應用中，我們主要考慮最大堆（也稱大頂堆）和最小堆（小頂堆）。其中最大堆（Max Heap）的根節點關鍵字（key）為所有節點關鍵字中最大值，且要求所有節點關鍵字的值大于等于其左孩子和右孩子的關鍵字。最小堆同理。以下主要以最大堆為例。
定義堆中節點的高度為根節點到所有葉子節點的最長簡單路徑上邊的數目，即對應完全二叉樹的高度。可證明節點數為n的堆高度為 ⌊log2n⌋ ⌊ log 2 n ⌋ 。即堆高度為 Θ(log2n) Θ ( log 2 n ) 。
維護堆的性質
Max_Heapify是用來維護最大堆性質的過程。
過程描述：輸入數組A及下标i。假定此時節點 i 的左子樹和右子樹都是最大堆。但是節點 i 關鍵字可能小于其孩子。而Max_Heapify則可以通過讓A[i]的值逐級下降，進而使根節點為 i 的子樹重新遵循最大堆。
因為堆高度為 Θ(log2n) Θ ( log 2 n ) ，是以Max_Heapify過程時間複雜度為 O(log2n) O ( l o g 2 n ) 。
僞代碼描述如下：
Max_Heapify(A,i)
l = Left(i)
r = Right(i)
largest = i
if l<=A.Heap_Size and A[l]>A[i] //A.Heap_Size表示存放在數組A中的有效堆元素
largest = l
if r<=A.Heap_Size and A[r]>A[i]
largest = r
if largest != i
exchange A[i] with A[largest]
Max_Heapify(A,largest)
C++實作：
這裡在實作中為了友善和清晰舍棄了下标為0的存儲位置，從下标1開始存放元素，初始化時數組大小為n+1，使其下标等于節點标号。
void Max_Heapify(int A[],int i,int n) //n即為A.Heap_Size
{
int largest=i;
if(*i<=n && A[*i]>A[largest])
{
largest = *i;
}
if(*i+<=n && A[*i+]>A[largest])
{
largest = *i+;
}
if(largest != i)
{
swap(A[i],A[largest]);
Max_Heapify(A,largest,n);
}
}
建堆
建堆指輸入一個數組，将其轉化為最大堆。利用上面的Max_Heapify過程完成。
思路：從n/2遞減到1依次調用Max_Heapify即可實作。
僞代碼：
Build_Max_Heap(A)
A.Heap_Size = A.length
for i=A.length/ downto
Max_Heapify(A,i)
C++實作：
void Build_Max_Heap(int A[],int n)
{
for(int i=n/;i>=;i--)
{
Max_Heapify(A,i,n);
}
}
堆排序
堆排序是一個經典的排序算法，借助最大堆（最小堆）完成。
過程描述：輸入數組A，n=A.length,将數組中元素按升序排列。
思路：堆中的最大元素總是在根節點A[1]，将其與堆中最後一個元素（A[n]）交換，并從堆中去掉最後一個節點（通過A.Heap_Size自減1實作）。為了維護最大堆的性質，需要在交換後調用Max_Heapify(A,1)，進而使A[1…n-1]構造成一個新的最大堆。重複這一過程直到堆大小下降為2。
步驟：
1. 将數組A建堆
2. 交換A[1]和堆中最後一個元素，堆大小減1
3. 維護根節點堆的性質，将最大元素置為根節點
4. 重複2,3直到排序完成
僞代碼：
Heap_Sort(A)
Build_Max_Heap(A)
for i=A.length downto
exchange A[] with A[i]
A.Heap_Size --
Max_Heapify(A,)
C++實作：
void Heap_Sort(int A[],int n)
{
Build_Max_Heap(A,n);
for(int i=n;i>=;i--)
{
swap(A[],A[i]); //A[i]為堆中最後一個元素
Max_Heapify(A,,i-); //i-1為堆中元素個數
}
}
void swap(int &x,int &y)
{
int temp = x;
x = y;
y = temp;
}
堆排序完整Test代碼:
//堆排序
#include<iostream>
#include<stdlib.h>
using namespace std;
void Max_Heapify(int A[],int i,int n);
void Build_Max_Heap(int A[],int n);
void Heap_Sort(int A[],int n);
void swap(int &x,int &y);
void Disp(int A[],int n);
int main(void)
{
int n;
cin >> n;
int A[n+];
for(int i=;i<=n;i++)
{
cin >> A[i];
}
Disp(A,n);
Heap_Sort(A,n);
Disp(A,n);
system("pause");
return ;
}
void swap(int &x,int &y)
{
int temp = x;
x = y;
y = temp;
}
void Max_Heapify(int A[],int i,int n)
{
int largest=i;
if(*i<=n && A[*i]>A[largest])
{
largest = *i;
}
if(*i+<=n && A[*i+]>A[largest])
{
largest = *i+;
}
if(largest != i)
{
swap(A[i],A[largest]);
Max_Heapify(A,largest,n);
}
}
void Build_Max_Heap(int A[],int n)
{
for(int i=n/;i>=;i--)
{
Max_Heapify(A,i,n);
}
}
void Heap_Sort(int A[],int n)
{
Build_Max_Heap(A,n);
for(int i=n;i>=;i--)
{
swap(A[],A[i]);
Max_Heapify(A,,i-);
}
}
void Disp(int A[],int n)
{
for(int i=;i<n;i++)
{
cout << A[i] << ",";
}
cout << A[n] << endl;
}
優先隊列
坑已填，見優先隊列 & 堆。——2018.3.24
參考資料：算法導論
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)