C++數(shù)據(jù)結(jié)構(gòu)之堆詳解
更新時間：2022年04月09日 17:02:47 作者：CairBin
本文詳細(xì)講解了C++數(shù)據(jù)結(jié)構(gòu)之堆，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下
堆的概念
堆（heap）是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個可以被看做一棵樹的數(shù)組對象，即是一種順序儲存結(jié)構(gòu)的完全二叉樹。
提示：完全二叉樹
完全二叉樹：對一棵深度為k、有n個結(jié)點(diǎn)二叉樹編號后，各節(jié)點(diǎn)的編號與深度為k的滿二叉樹相同位置的結(jié)點(diǎn)的編號相同，這顆二叉樹就被稱為完全二叉樹。[2]
堆的性質(zhì)
- 堆中某個結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值
- 堆總是一棵完全二叉樹
- 除了根結(jié)點(diǎn)和最后一個左子結(jié)點(diǎn)可以沒有兄弟結(jié)點(diǎn)，其他結(jié)點(diǎn)必須有兄弟結(jié)點(diǎn)
最大堆最小堆
最大堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最大者，且每個結(jié)點(diǎn)的值都比其孩子的值大。
最小堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最小者，且每個結(jié)點(diǎn)的值都比其孩子的值小。
代碼
定義
有限數(shù)組形式
int Heap[1024]; //順序結(jié)構(gòu)的二叉樹
若某結(jié)點(diǎn)編號為i，且存在左兒子和右兒子，則他們分別對應(yīng)
Heap[i*2+1]; //左兒子 Heap[i*2+2]; //右兒子
其父節(jié)點(diǎn)
Heap[i/2]; //i的父節(jié)點(diǎn)
動態(tài)數(shù)組形式
在項(xiàng)目開發(fā)中，經(jīng)常以動態(tài)數(shù)組形式出現(xiàn)，在本文主要對這種形式進(jìn)行介紹
//默認(rèn)容量
#define DEFAULT_CAPCITY 128
typedef struct _Heap
{
int *arr; //儲存元素的動態(tài)數(shù)組
int size; //元素個數(shù)
int capacity; //當(dāng)前存儲的容量
}Heap;操作
只使用InitHeap()函數(shù)進(jìn)行初始化即可，AdjustDown()與BuildHeap()僅為堆建立時的內(nèi)部調(diào)用
向下調(diào)整結(jié)點(diǎn)
- 以創(chuàng)建最大堆為例
- 將“判斷最大子結(jié)點(diǎn)是否大于當(dāng)前父結(jié)點(diǎn)”處的>=改為<=即可創(chuàng)建最小堆
//向下調(diào)整，將當(dāng)前結(jié)點(diǎn)與其子結(jié)點(diǎn)調(diào)整為最大堆
//用static修飾禁止外部調(diào)用
static void AdjustDown(Heap& heap, int index)
{
int cur = heap.arr[index]; //當(dāng)前待調(diào)整結(jié)點(diǎn)
int parent, child;
/*
判斷是否存在子結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)。
若不存在，堆是平衡的，則不調(diào)整；
若存在，則與最大子結(jié)點(diǎn)與之交換，交換后該子節(jié)點(diǎn)若還有子結(jié)點(diǎn)，則以此方法繼續(xù)調(diào)整。
*/
for (parent = index; (parent * 2 + 1) < heap.size; parent = child)
{
child = parent * 2 + 1; //左子結(jié)點(diǎn)
//取兩個子結(jié)點(diǎn)中最大節(jié)點(diǎn),(child+1)<heap.size防止越界
if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1])))
child++;
//判斷最大子結(jié)點(diǎn)是否大于當(dāng)前父結(jié)點(diǎn)
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，則使用默認(rèn)量，否則為size
int capacity = DEFAULT_CAPCITY>size?DEFAULT_CAPCITY:size;
heap.arr = new int[capacity]; //分配內(nèi)存，類型根據(jù)實(shí)際需要可修改
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;
}打印堆
- 實(shí)際上是一個層序遍歷[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;
//默認(rèn)容量
#define DEFAULT_CAPCITY 128
typedef struct _Heap {
int* arr;
int size;
int capacity;
}Heap;
//向下調(diào)整，將當(dāng)前結(jié)點(diǎn)與其子結(jié)點(diǎn)調(diào)整為最大堆
static void AdjustDown(Heap& heap, int index)
{
int cur = heap.arr[index]; //當(dāng)前待調(diào)整結(jié)點(diǎn)
int parent, child;
/*
判斷是否存在子結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)。
若不存在，堆是平衡的，則不調(diào)整；
若存在，則與最大子結(jié)點(diǎn)與之交換，交換后該子節(jié)點(diǎn)若還有子結(jié)點(diǎn)，則以此方法繼續(xù)調(diào)整。
*/
for (parent = index; (parent * 2 + 1) < heap.size; parent = child)
{
child = parent * 2 + 1; //左子結(jié)點(diǎn)
//取兩個子結(jié)點(diǎn)中最大節(jié)點(diǎn),(child+1)<heap.size防止越界
if (((child + 1) < heap.size && (heap.arr[child] < heap.arr[child + 1])))
child++;
//判斷最大子結(jié)點(diǎn)是否大于當(dāng)前父結(jié)點(diǎn)
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，則使用默認(rèn)量，否則為size
int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;
heap.arr = new int[capacity]; //分配內(nèi)存，類型根據(jù)實(shí)際需要可修改
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并實(shí)現(xiàn)對象池
這篇文章主要介紹了C++中的new和delete并實(shí)現(xiàn)對象池,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了C++計(jì)算每個字符出現(xiàn)的次數(shù)的相關(guān)資料,需要的朋友可以參考下2016-05-05
這篇文章主要介紹了c++函數(shù)重載的相關(guān)知識，文章講解的非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-06-06
這篇文章主要給大家介紹了關(guān)于OpenCV相機(jī)標(biāo)定的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2022-03-03
本篇文章是對結(jié)構(gòu)體的定義以及使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++實(shí)現(xiàn)含附件的郵件發(fā)送功能
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)含附件的郵件發(fā)送功能，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-05-05
這篇文章主要介紹了C語言獲取文件長度的相關(guān)知識,包括使用標(biāo)準(zhǔn)庫方法和使用Linux系統(tǒng)調(diào)用,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下2023-10-10
C++中Semaphore內(nèi)核對象用法實(shí)例
這篇文章主要介紹了C++中Semaphore內(nèi)核對象用法實(shí)例,有助于深入了解信號量(Semaphore)的基本用法,需要的朋友可以參考下2014-10-10
這篇文章主要為大家詳細(xì)介紹了用C語言簡單實(shí)現(xiàn)掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08![QT實(shí)現(xiàn)將兩個時間相加的算法[hh:?mm?+?hh:?mm]的示例代碼](http://img.jbzj.com/images/xgimg/bcimg9.png)
QT實(shí)現(xiàn)將兩個時間相加的算法[hh:?mm?+?hh:?mm]的示例代碼
本文主要介紹了QT實(shí)現(xiàn)將兩個時間相加的算法[hh:?mm?+?hh:?mm]的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07