[數(shù)據(jù)結(jié)構(gòu)]二叉樹(shù)--堆-創(chuàng)新互聯(lián)

image.png

創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括瀏陽(yáng)網(wǎng)站建設(shè)、瀏陽(yáng)網(wǎng)站制作、瀏陽(yáng)網(wǎng)頁(yè)制作以及瀏陽(yáng)網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，瀏陽(yáng)網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到瀏陽(yáng)省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！堆
    • 什么是堆
    • 堆的實(shí)現(xiàn)
        • 類的定義
        • 構(gòu)造函數(shù)
        • 析構(gòu)函數(shù)
        • push
        • 向上調(diào)整
        • 判斷堆是否為空
        • 返回堆中有效數(shù)據(jù)個(gè)數(shù)
        • 返回堆頂?shù)臄?shù)據(jù)
        • pop數(shù)據(jù),刪除堆頂?shù)臄?shù)據(jù)
        • 向下調(diào)整
    • 堆的應(yīng)用
        • TopK問(wèn)題
        • 堆排序
          • 1.第一種建堆方式-->向上調(diào)整
          • 2.第二種建堆方式--->向下調(diào)整
          • 排序
    • 總結(jié)

什么是堆

注意大家在學(xué)習(xí)編程的過(guò)程中, 肯定聽(tīng)說(shuō)過(guò)內(nèi)存中的堆和棧以及靜態(tài)區(qū)這種的, 這些是屬于操作系統(tǒng)虛擬進(jìn)程地址空間中的,
我們要說(shuō)的堆和這個(gè)并不是一回事,堆是二叉樹(shù)的一種, 是數(shù)據(jù)結(jié)構(gòu)的一種,我們來(lái)看看吧

普通的二叉樹(shù)不使用數(shù)組來(lái)存儲(chǔ),只有堆用數(shù)組來(lái)存儲(chǔ),
所以說(shuō)堆的邏輯結(jié)構(gòu)是二叉樹(shù), 物理結(jié)構(gòu)是數(shù)組

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

堆的性質(zhì):

  1. 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
  2. 堆總是一棵完全二叉樹(shù)。

小堆: 子節(jié)點(diǎn)都比不小于父節(jié)點(diǎn)

image.png
大堆
image.png

那我們嘗試用數(shù)組來(lái)實(shí)現(xiàn)這種數(shù)據(jù)結(jié)構(gòu)

堆的實(shí)現(xiàn)

那我們來(lái)分析一下堆這個(gè)類中需要哪些成員,image.png

類的定義
templateclass Heap
{public:
	Heap();
	void push(T val);
	void pop();
	T Top();
	bool empty();
	size_t size();
	~Heap();

private:
	T* _data;
	int _top;//指向最后一個(gè)數(shù)據(jù)的下一個(gè)位置
	int _capacity;
};
構(gòu)造函數(shù)

默認(rèn)構(gòu)造就是把成員都初始化一下,我這里沒(méi)有開(kāi)默認(rèn)空間, 大家可以選擇開(kāi)

Heap()
:_data(nullptr)
, _top(0)
, _capacity(0)
{}
析構(gòu)函數(shù)

析構(gòu)函數(shù)進(jìn)行資源清理,所以要把申請(qǐng)的空間都釋放掉

~Heap()
{free(_data);
	_top = _capactiy = 0;
}
push

push就是插入一個(gè)數(shù)據(jù),堆這里的插入和其他數(shù)據(jù)結(jié)構(gòu)不同, 堆插入任何一個(gè)數(shù)據(jù)都要保證堆的特性, 不可以本來(lái)是堆,最后不是堆, 我們來(lái)分析一下,我們這里都以建大堆為例子

image.png

插入的代碼比較簡(jiǎn)單,關(guān)鍵是向上調(diào)整,插入唯一需要注意的就是擴(kuò)容的問(wèn)題

void push(T val)
{//如果容量 == 個(gè)數(shù)
	if (_capacity == _top)
	{//擴(kuò)容 -- >2倍擴(kuò)容
		int newCapacity = _capacity == 0 ? 4 : _capacity * 2;
		T* ptr = (T*)realloc(_data, sizeof(T) * newCapacity);
		if (nullptr == ptr)
		{	perror("realloc fail");
			exit(-1);
		}
		_capacity = newCapacity;
		_data = ptr;
	}
	
	//擴(kuò)容完畢
	_data[_top] = val;
	//++ 長(zhǎng)度
	++_top;
	//向上調(diào)整
	AdjustUp(_data, _top - 1);
}
向上調(diào)整

為了保證堆的特性而向上調(diào)整,

image.png

那我們來(lái)分析一下這個(gè)向上調(diào)整該如何實(shí)現(xiàn)image.png

void AdjustUp(T* data, int child)
{int parent = (child - 1) / 2;
		while (child >0)
		{	//這里是以大堆為例,如果孩子大于父親, 那么就調(diào)整
			if (data[child] >data[parent])
			{		swap(data[child], data[parent]);
				//迭代
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{		break;
			}
}
判斷堆是否為空

這個(gè)相對(duì)比較簡(jiǎn)單

bool empty()
{//如果top等于0為空
		return _top == 0;
}
返回堆中有效數(shù)據(jù)個(gè)數(shù)
size_t size()
{return _top;
}
返回堆頂?shù)臄?shù)據(jù)

首先要判斷堆是否為空, 如果堆不為空, 還取個(gè)啥啊

T Top()
{assert(!empty());	
	return _data[_top - 1];
}
pop數(shù)據(jù),刪除堆頂?shù)臄?shù)據(jù)

我們來(lái)分析一下

image.png

void pop()
{assert(!empty());
		//交換堆頂?shù)臄?shù)據(jù)和最后一個(gè)數(shù)據(jù)
		swap(_data[0], _data[_top - 1]);

		--_top;
		//向下調(diào)整
		AdjustDown(_data, n, 0);
}
向下調(diào)整

image.png

核心思想就是如果大孩子大于根節(jié)點(diǎn), 就交換,直到最后歐一層

void AdjustDown(T* data, int n, int parent)
	{//先給出左孩子
		int child = parent * 2 + 1;

		while (child< n)
		{	//如果右孩子存在,并且比左孩子大
			if (child + 1< n && data[child + 1] >data[child])
				child++;
			if (data[child] >data[parent])
			{		swap(data[child], data[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{		break;
			}
		}
	}
堆的應(yīng)用 TopK問(wèn)題

關(guān)于TopK問(wèn)題,用堆解決是非常合適的問(wèn)題,我之前寫(xiě)過(guò)一篇 TopK問(wèn)題詳解

堆排序

堆排序是一種非常厲害的排序, 核心思想就利用了堆這種數(shù)據(jù)結(jié)構(gòu),我們來(lái)看看吧,我們距離

如果排升序的話,我們建小堆還是大堆呢??我們來(lái)分析一下
image.png
那我們?cè)撊绾谓ǘ涯?

1.第一種建堆方式–>向上調(diào)整

插入建堆

image.png

int arr[] = {6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(arr) / sizeof(int);

for (int i = 1; i< len; ++i)
{AdjustUp(arr, i);
}
2.第二種建堆方式—>向下調(diào)整

向下調(diào)整建堆就是二叉樹(shù)的典型分治思想,我們來(lái)分析一下

image.png

int arr[] = {6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(arr) / sizeof(int);

	//建堆 最后一個(gè)節(jié)點(diǎn)的下標(biāo)是len-1  ,所以它的父親下標(biāo)是(len-2)/2
for (int i = (len - 1 - 1) / 2; i >= 0; --i)
{AdjustDown(arr, len, i);
}

image.png

所以更推薦使用向下調(diào)整的方式來(lái)建堆,因?yàn)閺?fù)雜度比較低

排序

建好堆了以后就相對(duì)比較簡(jiǎn)單了,

利用堆的特性, pop的思想,把大的放到最后面, 然后調(diào)整前面的

void HeapSort(int* arr, int len)
{//建堆
	for (int i = (len - 1 - 1) / 2; i >= 0; --i)
	{AdjustDown(arr, len, i);
	}
	int end = len - 1;
	while (end >0)
	{swap(arr[0], arr[end]);
		AdjustDown(arr, end, 0);
		--end;
	}
}

建堆的復(fù)雜度O(N) , 調(diào)整的復(fù)雜度O(N* logN)

所以堆排序的復(fù)雜度就是O(N*logN)

總結(jié)

堆還是非常常用的,一定要利用堆的特性, 后面的優(yōu)先級(jí)隊(duì)列還會(huì)涉及到,
感謝收看
image.png

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前題目：[數(shù)據(jù)結(jié)構(gòu)]二叉樹(shù)--堆-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源：http://muchs.cn/article24/ceedce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、動(dòng)態(tài)網(wǎng)站、網(wǎng)站內(nèi)鏈、云服務(wù)器、電子商務(wù)、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)公司