C++數(shù)據(jù)結(jié)構(gòu)之堆詳解
堆的概念
堆(heap)是計算機科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個可以被看做一棵樹的數(shù)組對象,即是一種順序儲存結(jié)構(gòu)的完全二叉樹。
提示:完全二叉樹
完全二叉樹:對一棵深度為k、有n個結(jié)點二叉樹編號后,各節(jié)點的編號與深度為k的滿二叉樹相同位置的結(jié)點的編號相同,這顆二叉樹就被稱為完全二叉樹。[2]
堆的性質(zhì)
- 堆中某個結(jié)點的值總是不大于或不小于其父結(jié)點的值
- 堆總是一棵完全二叉樹
- 除了根結(jié)點和最后一個左子結(jié)點可以沒有兄弟結(jié)點,其他結(jié)點必須有兄弟結(jié)點
最大堆最小堆
最大堆:根結(jié)點的鍵值是所有堆結(jié)點鍵值中最大者,且每個結(jié)點的值都比其孩子的值大。
最小堆:根結(jié)點的鍵值是所有堆結(jié)點鍵值中最小者,且每個結(jié)點的值都比其孩子的值小。
代碼
定義
有限數(shù)組形式
int Heap[1024]; //順序結(jié)構(gòu)的二叉樹
若某結(jié)點編號為i,且存在左兒子和右兒子,則他們分別對應(yīng)
Heap[i*2+1]; //左兒子 Heap[i*2+2]; //右兒子
其父節(jié)點
Heap[i/2]; //i的父節(jié)點
動態(tài)數(shù)組形式
在項目開發(fā)中,經(jīng)常以動態(tài)數(shù)組形式出現(xiàn),在本文主要對這種形式進行介紹
//默認容量 #define DEFAULT_CAPCITY 128 typedef struct _Heap { int *arr; //儲存元素的動態(tài)數(shù)組 int size; //元素個數(shù) int capacity; //當前存儲的容量 }Heap;
操作
只使用InitHeap()函數(shù)進行初始化即可,AdjustDown()與BuildHeap()僅為堆建立時的內(nèi)部調(diào)用
向下調(diào)整結(jié)點
- 以創(chuàng)建最大堆為例
- 將“判斷最大子結(jié)點是否大于當前父結(jié)點”處的>=改為<=即可創(chuàng)建最小堆
//向下調(diào)整,將當前結(jié)點與其子結(jié)點調(diào)整為最大堆 //用static修飾禁止外部調(diào)用 static void AdjustDown(Heap& heap, int index) { int cur = heap.arr[index]; //當前待調(diào)整結(jié)點 int parent, child; /* 判斷是否存在子結(jié)點大于當前結(jié)點。 若不存在,堆是平衡的,則不調(diào)整; 若存在,則與最大子結(jié)點與之交換,交換后該子節(jié)點若還有子結(jié)點,則以此方法繼續(xù)調(diào)整。 */ for (parent = index; (parent * 2 + 1) < heap.size; parent = child) { child = parent * 2 + 1; //左子結(jié)點 //取兩個子結(jié)點中最大節(jié)點,(child+1)<heap.size防止越界 if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1]))) child++; //判斷最大子結(jié)點是否大于當前父結(jié)點 if (cur >= heap.arr[child]) //將此處的>=改成<=可構(gòu)建最小堆 { //不大于,不需要調(diào)整 break; } else { //大于,則交換 heap.arr[parent] = heap.arr[child]; heap.arr[child] = cur; } } }
建立堆
//建立堆,用static修飾禁止外部調(diào)用 static void BuildHeap(Heap& heap) { int i; //從倒數(shù)第二層開始調(diào)整(若只有一層則從該層開始) for (i = heap.size / 2 - 1; i >= 0; i--) { AdjustDown(heap, i); } }
初始化
//初始化堆 //參數(shù):被初始化的堆,存放初始數(shù)據(jù)的數(shù)組, 數(shù)組大小 bool InitHeap(Heap &heap, int *orginal, int size) { //若容量大于size,則使用默認量,否則為size int capacity = DEFAULT_CAPCITY>size?DEFAULT_CAPCITY:size; heap.arr = new int[capacity]; //分配內(nèi)存,類型根據(jù)實際需要可修改 if(!heap.arr) return false; //內(nèi)存分配失敗則返回False heap.capacity = capacity; //容量 heap.size = 0; //元素個數(shù)置為0 //若存在原始數(shù)組則構(gòu)建堆 if(size>0) { /* 內(nèi)存拷貝,將orginal的元素拷貝到堆數(shù)組arr中 size*sizeof(int)為元素所占內(nèi)存空間大小 */ memcpy(heap.arr,orginal, size*sizeof(int)); heap.size = size; //調(diào)整大小 BuildHeap(heap); //建堆 } return true; }
打印堆
- 實際上是一個層序遍歷[4]
//以樹狀的形式打印堆 void PrintHeapAsTreeStyle(Heap hp) { queue<int> que; int r = 0; que.push(r); queue<int> temp; while (!que.empty()) { r = que.front(); que.pop(); if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1); if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2); if (que.empty()) { cout << hp.arr[r] << endl; que = temp; temp = queue<int>(); } else cout << hp.arr[r] << " "; } }
測試
main函數(shù)
int main() { Heap hp; int vals[] = { 1,2,3,87,93,82,92,86,95 }; if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0]))) { fprintf(stderr, "初始化堆失??!\n"); exit(-1); } PrintHeapAsTreeStyle(hp); return 0; }
結(jié)果
95 93 92 87 1 82 3 86 2
完整代碼
#include <iostream> #include <queue> using namespace std; //默認容量 #define DEFAULT_CAPCITY 128 typedef struct _Heap { int* arr; int size; int capacity; }Heap; //向下調(diào)整,將當前結(jié)點與其子結(jié)點調(diào)整為最大堆 static void AdjustDown(Heap& heap, int index) { int cur = heap.arr[index]; //當前待調(diào)整結(jié)點 int parent, child; /* 判斷是否存在子結(jié)點大于當前結(jié)點。 若不存在,堆是平衡的,則不調(diào)整; 若存在,則與最大子結(jié)點與之交換,交換后該子節(jié)點若還有子結(jié)點,則以此方法繼續(xù)調(diào)整。 */ for (parent = index; (parent * 2 + 1) < heap.size; parent = child) { child = parent * 2 + 1; //左子結(jié)點 //取兩個子結(jié)點中最大節(jié)點,(child+1)<heap.size防止越界 if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1]))) child++; //判斷最大子結(jié)點是否大于當前父結(jié)點 if (cur >= heap.arr[child]) //將此處的>=改成<=可構(gòu)建最小堆 { //不大于,不需要調(diào)整 break; } else { //大于,則交換 heap.arr[parent] = heap.arr[child]; heap.arr[child] = cur; } } } //建立堆,用static修飾禁止外部調(diào)用 static void BuildHeap(Heap& heap) { int i; //從倒數(shù)第二層開始調(diào)整(若只有一層則從該層開始) for (i = heap.size / 2 - 1; i >= 0; i--) { AdjustDown(heap, i); } } //初始化堆 //參數(shù):被初始化的堆,存放初始數(shù)據(jù)的數(shù)組, 數(shù)組大小 bool InitHeap(Heap& heap, int* orginal, int size) { //若容量大于size,則使用默認量,否則為size int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size; heap.arr = new int[capacity]; //分配內(nèi)存,類型根據(jù)實際需要可修改 if (!heap.arr) return false; //內(nèi)存分配失敗則返回False heap.capacity = capacity; //容量 heap.size = 0; //元素個數(shù)置為0 //若存在原始數(shù)組則構(gòu)建堆 if (size > 0) { /* 內(nèi)存拷貝,將orginal的元素拷貝到堆數(shù)組arr中 size*sizeof(int)為元素所占內(nèi)存空間大小 */ memcpy(heap.arr, orginal, size * sizeof(int)); heap.size = size; //調(diào)整大小 BuildHeap(heap); //建堆 } return true; } //以樹狀的形式打印堆 void PrintHeapAsTreeStyle(Heap hp) { queue<int> que; int r = 0; que.push(r); queue<int> temp; while (!que.empty()) { r = que.front(); que.pop(); if (r * 2 + 1 < hp.size) temp.push(r * 2 + 1); if (r * 2 + 2 < hp.size) temp.push(r * 2 + 2); if (que.empty()) { cout << hp.arr[r] << endl; que = temp; temp = queue<int>(); } else cout << hp.arr[r] << " "; } } int main() { Heap hp; int vals[] = { 1,2,3,87,93,82,92,86,95 }; if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0]))) { fprintf(stderr, "初始化堆失敗!\n"); exit(-1); } PrintHeapAsTreeStyle(hp); return 0; }
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
深入理解C++中的new和delete并實現(xiàn)對象池
這篇文章主要介紹了C++中的new和delete并實現(xiàn)對象池,本文通過實例代碼給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-09-09QT實現(xiàn)將兩個時間相加的算法[hh:?mm?+?hh:?mm]的示例代碼
本文主要介紹了QT實現(xiàn)將兩個時間相加的算法[hh:?mm?+?hh:?mm]的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07