數(shù)據(jù)結(jié)構(gòu)之堆詳解
1. 概述
堆(也叫優(yōu)先隊(duì)列),是一棵完全二叉樹,它的特點(diǎn)是父節(jié)點(diǎn)的值大于(小于)兩個(gè)子節(jié)點(diǎn)的值(分別稱為大頂堆和小頂堆)。它常用于管理算法執(zhí)行過程中的信息,應(yīng)用場(chǎng)景包括堆排序,優(yōu)先隊(duì)列等。
2. 堆的基本操作
堆是一棵完全二叉樹,高度為O(lg n),其基本操作至多與樹的高度成正比。在介紹堆的基本操作之前,先介紹幾個(gè)基本術(shù)語(yǔ):
A:用于表示堆的數(shù)組,下標(biāo)從1開始,一直到n
PARENT(t):節(jié)點(diǎn)t的父節(jié)點(diǎn),即floor(t/2)
RIGHT(t):節(jié)點(diǎn)t的左孩子節(jié)點(diǎn),即:2*t
LEFT(t):節(jié)點(diǎn)t的右孩子節(jié)點(diǎn),即:2*t+1
HEAP_SIZE(A):堆A當(dāng)前的元素?cái)?shù)目
下面給出其主要的四個(gè)操作(以大頂堆為例):
2.1 Heapify(A,n,t)
該操作主要用于維持堆的基本性質(zhì)。假定以RIGHT(t)和LEFT(t)為根的子樹都已經(jīng)是堆,然后調(diào)整以t為根的子樹,使之成為堆。
void Heapify(int A[], int n, int t)
{
int left = LEFT(t);
int right = RIGHT(t);
int max = t;
if(left <= n) max = A[left] > A[max] ? left : max;
if(right <= n) max = A[right] > A[max] ? right : max;
if(max != A[t])
{
swap(A, max, t);
Heapify(A, n, max);
}
}
2.2 BuildHeap(A,n)
該操作主要是將數(shù)組A轉(zhuǎn)化成一個(gè)大頂堆。思想是,先找到堆的最后一個(gè)非葉子節(jié)點(diǎn)(即為第n/2個(gè)節(jié)點(diǎn)),然后從該節(jié)點(diǎn)開始,從后往前逐個(gè)調(diào)整每個(gè)子樹,使之稱為堆,最終整個(gè)數(shù)組便是一個(gè)堆。
void BuildHeap(int A[], int n)
{
int i;
for(i = n/2; i<=n; i++)
Heapify(A, n, i);
}
2.3 GetMaximum(A,n)
該操作主要是獲取堆中最大的元素,同時(shí)保持堆的基本性質(zhì)。堆的最大元素即為第一個(gè)元素,將其保存下來,同時(shí)將最后一個(gè)元素放到A[1]位置,之后從上往下調(diào)整A,使之成為一個(gè)堆。
void GetMaximum(int A[], int n)
{
int max = A[1];
A[1] = A[n];
n--;
Heapify(A, n, 1);
return max;
}
2.4 Insert(A, n, t)
向堆中添加一個(gè)元素t,同時(shí)保持堆的性質(zhì)。算法思想是,將t放到A的最后,然后從該元素開始,自下向上調(diào)整,直至A成為一個(gè)大頂堆。
void Insert(int A[], int n, int t)
{
n++;
A[n] = t;
int p = n;
while(p >1 && A[PARENT(p)] < t)
{
A[p] = A[PARENT(p)];
p = PARENT(p);
}
A[p] = t;
return max;
}
3. 堆的應(yīng)用
3.1 堆排序
堆的最常見應(yīng)用是堆排序,時(shí)間復(fù)雜度為O(N lg N)。如果是從小到大排序,用大頂堆;從大到小排序,用小頂堆。
3.2 在O(n lg k)時(shí)間內(nèi),將k個(gè)排序表合并成一個(gè)排序表,n為所有有序表中元素個(gè)數(shù)。
【解析】取前100 萬個(gè)整數(shù),構(gòu)造成了一棵數(shù)組方式存儲(chǔ)的具有小頂堆,然后接著依次取下一個(gè)整數(shù),如果它大于最小元素亦即堆頂元素,則將其賦予堆頂元素,然后用Heapify調(diào)整整個(gè)堆,如此下去,則最后留在堆中的100萬個(gè)整數(shù)即為所求 100萬個(gè)數(shù)字。該方法可大大節(jié)約內(nèi)存。
3.3 一個(gè)文件中包含了1億個(gè)隨機(jī)整數(shù),如何快速的找到最大(小)的100萬個(gè)數(shù)字?(時(shí)間復(fù)雜度:O(n lg k))
4. 總結(jié)
堆是一種非常基礎(chǔ)但很實(shí)用的數(shù)據(jù)結(jié)構(gòu),很多復(fù)雜算法或者數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)就是堆,因而,了解和掌握堆這種數(shù)據(jù)結(jié)構(gòu)顯得尤為重要。
5. 參考資料
(1)經(jīng)典算法教程《算法導(dǎo)論》
相關(guān)文章
c語(yǔ)言switch反匯編的實(shí)現(xiàn)
本文主要介紹了c語(yǔ)言switch反匯編,在分支較多的時(shí)候,switch的效率比if高,在反匯編中我們即可看到效率高的原因,感興趣的可以了解一下2021-06-06c++中關(guān)于max_element()函數(shù)解讀
這篇文章主要介紹了c++中關(guān)于max_element()函數(shù)解讀,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-02-02C語(yǔ)言fgetc和fputc函數(shù)用法詳解(以字符形式讀寫文件)
這篇文章主要介紹了C語(yǔ)言fgetc和fputc函數(shù)用法詳解(以字符形式讀寫文件),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01C++使用鏈表存儲(chǔ)實(shí)現(xiàn)通訊錄功能管理
這篇文章主要為大家詳細(xì)介紹了C++使用鏈表存儲(chǔ)實(shí)現(xiàn)通訊錄功能管理,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-06-06