[數據結構]二叉樹--堆-創新互聯

創新互聯公司服務項目包括瀏陽網站建設、瀏陽網站制作、瀏陽網頁制作以及瀏陽網絡營銷策劃等。多年來，我們專注于互聯網行業，利用自身積累的技術優勢、行業經驗、深度合作伙伴關系等，向廣大中小型企業、政府機構等提供互聯網行業的解決方案，瀏陽網站推廣取得了明顯的社會效益與經濟效益。目前，我們服務的客戶以成都為中心已經輻射到瀏陽省份的部分城市，未來相信會繼續擴大服務區域并繼續獲得客戶的支持與信任！堆

- 什么是堆
- 堆的實現
- - - 類的定義
    - 構造函數
    - 析構函數
    - push
    - 向上調整
    - 判斷堆是否為空
    - 返回堆中有效數據個數
    - 返回堆頂的數據
    - pop數據,刪除堆頂的數據
    - 向下調整
- 堆的應用
- - - TopK問題
    - 堆排序
    - - 1.第一種建堆方式-->向上調整
      - 2.第二種建堆方式--->向下調整
      - 排序
- 總結

什么是堆

注意大家在學習編程的過程中, 肯定聽說過內存中的堆和棧以及靜態區這種的, 這些是屬于操作系統虛擬進程地址空間中的,
我們要說的堆和這個并不是一回事,堆是二叉樹的一種, 是數據結構的一種,我們來看看吧

普通的二叉樹不使用數組來存儲,只有堆用數組來存儲,
所以說堆的邏輯結構是二叉樹, 物理結構是數組

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

堆的性質:
堆中某個節點的值總是不大于或不小于其父節點的值；
堆總是一棵完全二叉樹。

小堆: 子節點都比不小于父節點

大堆

那我們嘗試用數組來實現這種數據結構

堆的實現

那我們來分析一下堆這個類中需要哪些成員,

類的定義

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

private:
	T* _data;
	int _top;//指向最后一個數據的下一個位置
	int _capacity;
};

構造函數

默認構造就是把成員都初始化一下,我這里沒有開默認空間, 大家可以選擇開

Heap()
:_data(nullptr)
, _top(0)
, _capacity(0)
{}

析構函數

析構函數進行資源清理,所以要把申請的空間都釋放掉

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

push

push就是插入一個數據,堆這里的插入和其他數據結構不同, 堆插入任何一個數據都要保證堆的特性, 不可以本來是堆,最后不是堆, 我們來分析一下,我們這里都以建大堆為例子

插入的代碼比較簡單,關鍵是向上調整,插入唯一需要注意的就是擴容的問題

void push(T val)
{//如果容量 == 個數
	if (_capacity == _top)
	{//擴容 -- >2倍擴容
		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;
	}
	
	//擴容完畢
	_data[_top] = val;
	//++ 長度
	++_top;
	//向上調整
	AdjustUp(_data, _top - 1);
}

向上調整

為了保證堆的特性而向上調整,

那我們來分析一下這個向上調整該如何實現

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

判斷堆是否為空

這個相對比較簡單

bool empty()
{//如果top等于0為空
		return _top == 0;
}

返回堆中有效數據個數

size_t size()
{return _top;
}

返回堆頂的數據

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

T Top()
{assert(!empty());	
	return _data[_top - 1];
}

pop數據,刪除堆頂的數據

我們來分析一下

void pop()
{assert(!empty());
		//交換堆頂的數據和最后一個數據
		swap(_data[0], _data[_top - 1]);

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

向下調整

核心思想就是如果大孩子大于根節點, 就交換,直到最后歐一層

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;
			}
		}
	}

堆的應用 TopK問題

關于TopK問題,用堆解決是非常合適的問題,我之前寫過一篇 TopK問題詳解

堆排序

堆排序是一種非常厲害的排序, 核心思想就利用了堆這種數據結構,我們來看看吧,我們距離

如果排升序的話,我們建小堆還是大堆呢??我們來分析一下

那我們該如何建堆呢?

1.第一種建堆方式–>向上調整

插入建堆

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.第二種建堆方式—>向下調整

向下調整建堆就是二叉樹的典型分治思想,我們來分析一下

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

	//建堆 最后一個節點的下標是len-1  ,所以它的父親下標是(len-2)/2
for (int i = (len - 1 - 1) / 2; i >= 0; --i)
{AdjustDown(arr, len, i);
}

所以更推薦使用向下調整的方式來建堆,因為復雜度比較低

排序

建好堆了以后就相對比較簡單了,

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

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;
	}
}