C++數(shù)據(jù)結(jié)構(gòu)之堆詳解
更新時(shí)間：2022年04月09日 17:02:47 作者：CairBin
本文詳細(xì)講解了C++數(shù)據(jù)結(jié)構(gòu)之堆，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
堆的概念
堆（heap）是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個(gè)可以被看做一棵樹的數(shù)組對(duì)象，即是一種順序儲(chǔ)存結(jié)構(gòu)的完全二叉樹。
提示：完全二叉樹
完全二叉樹：對(duì)一棵深度為k、有n個(gè)結(jié)點(diǎn)二叉樹編號(hào)后，各節(jié)點(diǎn)的編號(hào)與深度為k的滿二叉樹相同位置的結(jié)點(diǎn)的編號(hào)相同，這顆二叉樹就被稱為完全二叉樹。[2]
堆的性質(zhì)
- 堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值
- 堆總是一棵完全二叉樹
- 除了根結(jié)點(diǎn)和最后一個(gè)左子結(jié)點(diǎn)可以沒有兄弟結(jié)點(diǎn)，其他結(jié)點(diǎn)必須有兄弟結(jié)點(diǎn)
最大堆最小堆
最大堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最大者，且每個(gè)結(jié)點(diǎn)的值都比其孩子的值大。
最小堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最小者，且每個(gè)結(jié)點(diǎn)的值都比其孩子的值小。
代碼
定義
有限數(shù)組形式
int Heap[1024]; //順序結(jié)構(gòu)的二叉樹
若某結(jié)點(diǎn)編號(hào)為i，且存在左兒子和右兒子，則他們分別對(duì)應(yīng)
Heap[i*2+1]; //左兒子 Heap[i*2+2]; //右兒子
其父節(jié)點(diǎn)
Heap[i/2]; //i的父節(jié)點(diǎn)
動(dòng)態(tài)數(shù)組形式
在項(xiàng)目開發(fā)中，經(jīng)常以動(dòng)態(tài)數(shù)組形式出現(xiàn)，在本文主要對(duì)這種形式進(jìn)行介紹
//默認(rèn)容量
#define DEFAULT_CAPCITY 128
typedef struct _Heap
{
int *arr; //儲(chǔ)存元素的動(dòng)態(tài)數(shù)組
int size; //元素個(gè)數(shù)
int capacity; //當(dāng)前存儲(chǔ)的容量
}Heap;操作
只使用InitHeap()函數(shù)進(jìn)行初始化即可，AdjustDown()與BuildHeap()僅為堆建立時(shí)的內(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)
//取兩個(gè)子結(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; //元素個(gè)數(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í)際上是一個(gè)層序遍歷[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] << " ";
}
}測(cè)試
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)
//取兩個(gè)子結(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; //元素個(gè)數(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)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:
- C++ 數(shù)據(jù)結(jié)構(gòu) 堆排序的實(shí)現(xiàn)
- C++程序內(nèi)存棧區(qū)與堆區(qū)模型案例分析
- c++深入淺出講解堆排序和堆
- 詳解C++內(nèi)存的代碼區(qū),全局區(qū),棧區(qū)和堆區(qū)
- C++實(shí)現(xiàn)堆排序?qū)嵗榻B
- 詳解c/c++鏈?zhǔn)蕉褩Ｃ枋鲞M(jìn)制轉(zhuǎn)換問題示例
- C++基礎(chǔ)算法基于哈希表的索引堆變形
- C/C++中棧(stack)&堆(heap)詳解及其作用介紹
- C++ 自由存儲(chǔ)區(qū)是否等價(jià)于堆你知道嗎
- C++實(shí)現(xiàn)堆排序示例
相關(guān)文章
C++中strlen函數(shù)的三種實(shí)現(xiàn)方法
在C語言中我們要獲取字符串的長度，可以使用strlen?函數(shù)，strlen?函數(shù)計(jì)算字符串的長度時(shí)，直到空結(jié)束字符，但不包括空結(jié)束字符，因?yàn)閟trlen函數(shù)時(shí)不包含最后的結(jié)束字符的，因此一般使用strlen函數(shù)計(jì)算的字符串的長度會(huì)比使用sizeof計(jì)算的字符串的字節(jié)數(shù)要小2022-05-05
這篇文章主要介紹了最新clion2020激活碼附安裝教程(親測(cè)有效),本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-11-11
C語言?超詳細(xì)梳理總結(jié)動(dòng)態(tài)內(nèi)存管理
動(dòng)態(tài)內(nèi)存是相對(duì)靜態(tài)內(nèi)存而言的。所謂動(dòng)態(tài)和靜態(tài)就是指內(nèi)存的分配方式。動(dòng)態(tài)內(nèi)存是指在堆上分配的內(nèi)存，而靜態(tài)內(nèi)存是指在棧上分配的內(nèi)存，本文帶你深入探究C語言中動(dòng)態(tài)內(nèi)存的管理2022-03-03
這篇文章主要介紹了C++實(shí)現(xiàn)堆排序示例，全文運(yùn)用大量代碼完成堆排序，需要了解的朋友可以參考一下這篇文章2021-08-08
這篇文章主要介紹了C++位操作的常見用法,包括了判斷奇偶、交換兩個(gè)數(shù)、正負(fù)轉(zhuǎn)換、求絕對(duì)值等,需要的朋友可以參考下2014-09-09
Qt串口通信開發(fā)之QSerialPort模塊簡(jiǎn)單使用方法與實(shí)例
這篇文章主要介紹了Qt串口通信開發(fā)之QSerialPort模塊簡(jiǎn)單使用方法與實(shí)例,需要的朋友可以參考下2020-03-03
C語言實(shí)現(xiàn)socket簡(jiǎn)單通信實(shí)例
這篇文章主要介紹了C語言實(shí)現(xiàn)socket簡(jiǎn)單通信的方法,是學(xué)習(xí)C語言網(wǎng)絡(luò)編程非?；A(chǔ)而又實(shí)用的實(shí)例,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了C語言中scanf函數(shù)的原樣輸入的坑及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要為大家詳細(xì)介紹了C++成員函數(shù)中const的使用，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03![淺析string 與char* char[]之間的轉(zhuǎn)換](http://img.jbzj.com/images/xgimg/bcimg9.png)
淺析string 與char* char[]之間的轉(zhuǎn)換
與char*不同的是，string不一定以NULL('\0')結(jié)束。string長度可以根據(jù)length()得到，string可以根據(jù)下標(biāo)訪問。所以，不能將string直接賦值給char*2013-10-10