18、二叉堆及其應用
(1)堆排序
<1> 二叉堆:二叉堆實際上一個完全二叉樹。
在最大堆中,父節(jié)點的值大于等于子節(jié)點的值,所以堆的最大值在根部;
在最小堆中,父節(jié)點的值小于等于子節(jié)點的值,所以堆的最小值在根部;
上圖是一個最小堆
<2>二叉堆可用于排序——復雜度為O(nlgn)
基本步驟有:
a. 建立二叉最大堆;
b. 由于最大值在根部,所以每次取出根部值和最后一個節(jié)點交換,堆的size減1,然后重新調(diào)整堆為最大堆,調(diào)整堆的復雜度為o(lgn)。
如何建立一個二叉最大堆呢?
根據(jù)完全二叉樹的特點,可以知道有孩子的節(jié)點的節(jié)點下標是[0, n/2-1],因此我們從n/2-1開始向上調(diào)整,使之符合父節(jié)點大于孩子節(jié)點這個最大堆的特點。
只要建好最大堆,接下來就是步驟2了,注意調(diào)整堆要從根節(jié)點開始調(diào)整,堆的大小要減一。注意:我們的下標從0開始的
堆排序源碼:
//i節(jié)點的父節(jié)點的下標
inlineint Parent(int i)
{
return (i-1)/2;
}
//i節(jié)點的左孩子的下標
inlineint Left(int i)
{
return 2*i+1;
}
//i節(jié)點的右孩子的下標
inlineint Right(int i)
{
return 2*i+2;
}
voidMaxHeapify(int a[],int heap_size,int i)
{
int left=Left(i);
int right=Right(i);
int largest=i;
if(left
largest=left;
if(right
largest=right;
if(largest!=i)
{
swap(a,i,largest);
MaxHeapify(a,heap_size,largest);
}
}
voidBuildMaxHeap(int a[],int n)
{
int i;
for(i=n/2-1;i>=0;i--)
MaxHeapify(a,n,i);
}
voidHeapSort(int a[],int n)
{
int i;
BuildMaxHeap(a,n);
for(i=n-1;i>0;i--)
{
swap(a,i,0);
MaxHeapify(a,i,0);
}
}
相關推薦:北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |