堆的概念

如果有一個(gè)關(guān)鍵碼的集合K={k0,k1,k2,…,kn-1},把它的所有元素按完全二叉樹(shù)的順序存儲(chǔ)方式存儲(chǔ)再一個(gè)一維數(shù)組中，并滿足:Ki<=K2i+1且Ki<=K2i+1(Ki >= K2i+1 且 Ki >= K2i+2),i=0,1,2,3…。則稱(chēng)為小堆(或大堆)。將根結(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根結(jié)點(diǎn)最小的堆叫做最小堆或小根堆

堆的性質(zhì)

堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；

堆總是一棵完全二叉樹(shù)。

堆的向下調(diào)整算法

順序存儲(chǔ)的完全二叉樹(shù)

已知[parent] [left] = 2*[parent]+1; [right] = 2*[parent]+2;已知[child] 無(wú)論左右 [parent] = ([child]-1)/2

基本步驟

建立小堆

要調(diào)整root所在結(jié)點(diǎn)，前提:root的左右結(jié)點(diǎn)子樹(shù)已經(jīng)滿足堆的性質(zhì)

如果root所在結(jié)點(diǎn)已經(jīng)是葉子結(jié)點(diǎn)，調(diào)整結(jié)束

找到左右孩子中最小的一個(gè)min

if (array[root] <= array[min])。調(diào)整結(jié)束

else: swap(&array[root],&array[min]) ; [min] = [root] ; 再回到1重復(fù)這幾個(gè)步驟

代碼實(shí)現(xiàn)

void AdjustDown(int array[], int size, int root) {//判斷 root 是否是葉子結(jié)點(diǎn)//因?yàn)?堆是完全二叉樹(shù)，所以沒(méi)有左孩子一定沒(méi)有右孩子//又因?yàn)槎咽琼樞虼鎯?chǔ)的//所以，找到左孩子的下標(biāo)，如果左孩子的下標(biāo)越界了，則沒(méi)有左孩子while (1){int left = 2 * root + 1;if (left >= size){//越界了，就是葉子結(jié)點(diǎn)return;}//走完上面一定有左孩子，判讀是否有右孩子//找到左右孩子最小的一個(gè)int right = 2 * root +2;int min = left;//最開(kāi)始就認(rèn)為最小的值為左孩子if (right < size && array[right] < array[left]){//沒(méi)有越界,就有右孩子，如果右孩子的值小于左孩子的值min = right;}//比較array[min] array[root]if (array[root] <= array[min]){return;}//調(diào)整,交換值int t = array[root];array[root] = array[min];array[min] = t;//需要繼續(xù)向下調(diào)整，以min作為結(jié)點(diǎn)root = min;} }

測(cè)試

void PrintArray(int array[], int size) {for (int i =0; i < size; ++i){printf("% d", array[i]);}printf("\n"); }void TestAdjustDown() {int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };int size = sizeof array / sizeof(int);PrintArray(array, size);AdjustDown(array, size, 0);PrintArray(array, size); }

時(shí)間復(fù)雜度(logn)

建堆

循環(huán)變量i從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，到0結(jié)束，在這之間不斷的做向下調(diào)整

最后一個(gè)非葉子節(jié)點(diǎn) = 最后一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)( size-1) = ((size-1)-1)/2

代碼實(shí)現(xiàn)

//建堆 void CreateHeap(int array[], int size) {for (int i = (size - 2) / 2; i >= 0; i--){//不斷的向下調(diào)整AdjustDown(array, size, i);} }

測(cè)試

時(shí)間復(fù)雜度O(n)

void TestCreateHeap(){int array[] = { 15, 37, 2, 45, 63, 9, 18, 7, 16, 13 };int size = sizeof(array) / sizeof(int);CreateHeap(array, size);PrintArray(array, size); }

堆的初始化

//初始化 void HeapInit(Heap *heap, int array[], int size){memcpy(heap->array, array, size*sizeof(int));heap->size = size;CreateHeap(heap->array, size); }

堆的刪除

只能刪除堆頂元素，刪其他位置沒(méi)有意義

拿數(shù)組中最后一個(gè)元素，覆蓋掉數(shù)組第一個(gè)元素，也就是堆頂元素，然后向下調(diào)整

代碼實(shí)現(xiàn)

//刪除 void HeapPop(Heap *heap) {heap->array[0] = heap->array[heap->size - 1];AdjustDown(heap->array, heap->size - 1,0);heap->size--; }

堆的插入

往數(shù)組中最后一個(gè)位置插入，然后向上調(diào)整

//向上調(diào)整 /* array 數(shù)組 size 數(shù)組的長(zhǎng)度 child 要向上調(diào)整的結(jié)點(diǎn)下標(biāo) *///小堆的情況 void AdjustUp(int array[], int size, int child) {while (1){//已經(jīng)到堆頂位置if (child == 0){return;}int parent = (child - 1) / 2;//父結(jié)點(diǎn)的值比孩子的值小的就不用調(diào)整if (array[parent] <= array[child]){return;}//交換int t = array[parent];array[parent] = array[child];array[child] = t;child = parent;} } /插入操作 void HeapPush(Heap *heap, int val){heap->array[heap->size++] = val;AdjustUp(heap->array, heap->size, heap->size - 1); }

堆排序

堆排序不能找最小的放到最前，要不然堆的結(jié)構(gòu)會(huì)被破壞

堆排序的注意事項(xiàng)

排升序，建大堆

排降序，建小堆

原因是，重新調(diào)整回堆的成本更小(向下調(diào)整(O(logn)) < 建堆(O(n)))

i的意義是被選出的最大的數(shù)的個(gè)數(shù) for(i < size-1){//一次循環(huán)，找出一個(gè)最大的數(shù)放到最后swap(&array[0],&array[size-1-i])AdjustDown(array,size-1-i); }

代碼實(shí)現(xiàn)

//大堆的情況void AdjustDown222(int array[], int size, int root) {//判斷 root 是否是葉子結(jié)點(diǎn)//因?yàn)?堆是完全二叉樹(shù)，所以沒(méi)有左孩子一定沒(méi)有右孩子//又因?yàn)槎咽琼樞虼鎯?chǔ)的//所以，找到左孩子的下標(biāo)，如果左孩子的下標(biāo)越界了，則沒(méi)有左孩子while (1){int left = 2 * root + 1;if (left >= size){//越界了，就是葉子結(jié)點(diǎn)return;}//走完上面一定有左孩子，判讀是否有右孩子//找到左右孩子最小的一個(gè)int right = 2 * root + 2;int min = left;//最開(kāi)始就認(rèn)為最小的值為左孩子if (right < size && array[right] > array[left]){//沒(méi)有越界,就有右孩子，如果右孩子的值小于左孩子的值min = right;}//比較array[min] array[root]if (array[root] >= array[min]){return;}//調(diào)整,交換值int t = array[root];array[root] = array[min];array[min] = t;//需要繼續(xù)向下調(diào)整，以min作為結(jié)點(diǎn)root = min;} } void AdjustUp222(int array[], int size, int child) {while (1){//已經(jīng)到堆頂位置if (child == 0){return;}int parent = (child - 1) / 2;//父結(jié)點(diǎn)的值比孩子的值小的就不用調(diào)整if (array[parent] >= array[child]){return;}//交換int t = array[parent];array[parent] = array[child];array[child] = t;child = parent;} }//堆排序 //升序，建大堆void HeapSort(int array[], int size) {CreateHeap(array, size);//i 表示被找出的最大的數(shù)的個(gè)數(shù)for (int i = 0; i < size - 1; i++){//每次循環(huán)，會(huì)找出最大的一個(gè)數(shù)放到最后int t = array[0];array[0] = array[size - i - 1];array[size - i - 1] = t;//進(jìn)行向下調(diào)整，數(shù)據(jù)規(guī)模是size-1-i;AdjustDown222(array, size - 1 - i, 0);} }

測(cè)試

void TestHeapSort() {int array[] = { 39, 129, 12, 38, 27, 9, 33, 2, 14 };int size = sizeof(array) / sizeof(int);HeapSort(array, size);PrintArray(array, size); }

測(cè)試堆排序與冒泡排序的速度

#define SIZE 50000void TestSortSpeed(){srand(20190104);int array[SIZE] ;for (int i = 0; i < SIZE; i++){array[i] = rand() % 10 * 10000;}int s = time();HeapSort(array, SIZE);int e = time();printf("%d\n", e - s);}

堆排序速度：

冒泡排序速度：

TopK問(wèn)題

在海量數(shù)據(jù)中(n>>100*10000),找最大的k=10個(gè)數(shù)

/* 類(lèi)似偽代碼，實(shí)際中，size是海量的，內(nèi)存中放不下，需要借助文件操作 */ void TopK(int array[], int size, int k){int *heap = (int *)malloc(sizeof(int)*k);for (int i = 0; i < k; i++){heap[i] = array[i];}//針對(duì)heap建小堆CreateHeap(heap, k);for (int j = k; j < size; j++){if (array[j]>heap[0]){heap[0] = array[j];AdjustDown(heap, k, 0);}} }

總結(jié)

以上是生活随笔為你收集整理的再写堆（堆的性质，向下调整，建堆，堆的插入删除初始化，堆排序，TopK问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。