欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++數(shù)據(jù)結(jié)構(gòu)之堆詳解

 更新時間:2022年04月09日 17:02:47   作者:CairBin  
本文詳細講解了C++數(shù)據(jù)結(jié)構(gòu)之堆,文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下

堆的概念

堆(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)對象池

    這篇文章主要介紹了C++中的new和delete并實現(xiàn)對象池,本文通過實例代碼給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-09-09
  • C++計算每個字符出現(xiàn)的次數(shù)

    C++計算每個字符出現(xiàn)的次數(shù)

    這篇文章主要介紹了C++計算每個字符出現(xiàn)的次數(shù)的相關(guān)資料,需要的朋友可以參考下
    2016-05-05
  • 詳解C++之函數(shù)重載

    詳解C++之函數(shù)重載

    這篇文章主要介紹了c++函數(shù)重載的相關(guān)知識,文章講解的非常細致,代碼幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下
    2020-06-06
  • OpenCV相機標定的全過程記錄

    OpenCV相機標定的全過程記錄

    這篇文章主要給大家介紹了關(guān)于OpenCV相機標定的相關(guān)資料,文中通過實例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2022-03-03
  • 解析結(jié)構(gòu)體的定義及使用詳解

    解析結(jié)構(gòu)體的定義及使用詳解

    本篇文章是對結(jié)構(gòu)體的定義以及使用進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05
  • C++實現(xiàn)含附件的郵件發(fā)送功能

    C++實現(xiàn)含附件的郵件發(fā)送功能

    這篇文章主要為大家詳細介紹了C++實現(xiàn)含附件的郵件發(fā)送功能,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-05-05
  • C語言獲取文件長度的方法

    C語言獲取文件長度的方法

    這篇文章主要介紹了C語言獲取文件長度的相關(guān)知識,包括使用標準庫方法和使用Linux系統(tǒng)調(diào)用,本文通過實例代碼給大家介紹的非常詳細,需要的朋友可以參考下
    2023-10-10
  • C++中Semaphore內(nèi)核對象用法實例

    C++中Semaphore內(nèi)核對象用法實例

    這篇文章主要介紹了C++中Semaphore內(nèi)核對象用法實例,有助于深入了解信號量(Semaphore)的基本用法,需要的朋友可以參考下
    2014-10-10
  • 用C語言簡單實現(xiàn)掃雷小游戲

    用C語言簡單實現(xiàn)掃雷小游戲

    這篇文章主要為大家詳細介紹了用C語言簡單實現(xiàn)掃雷小游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-08-08
  • QT實現(xiàn)將兩個時間相加的算法[hh:?mm?+?hh:?mm]的示例代碼

    QT實現(xiàn)將兩個時間相加的算法[hh:?mm?+?hh:?mm]的示例代碼

    本文主要介紹了QT實現(xiàn)將兩個時間相加的算法[hh:?mm?+?hh:?mm]的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-07-07

最新評論