有關(guān)二叉樹的性質(zhì)：

1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有 個(gè)結(jié)點(diǎn).

2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是 .

3. 對(duì)任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 , 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 ,則有 ＝ ＋1

4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h= . (ps： 是log以2 為底，n+1為對(duì)數(shù))

5. 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號(hào)，則對(duì) 于序號(hào)為i的結(jié)點(diǎn)有：

1. 若i>0，i位置節(jié)點(diǎn)的雙親序號(hào)：(i-1)/2；i=0，i為根節(jié)點(diǎn)編號(hào)，無(wú)雙親節(jié)點(diǎn)

2. 若2i+1<n,左孩子序號(hào)：2i+1 若2i+1>=n則無(wú)左孩子

3. 若2i+2<n,右孩子序號(hào)：2i+2 若2i+2>=n則無(wú)右孩子

有關(guān)堆

存儲(chǔ)結(jié)構(gòu)：

二叉樹一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

普通的二叉樹是不適合用數(shù)組來(lái)存儲(chǔ)的，因?yàn)榭赡軙?huì)存在大量的空間浪費(fèi)。而完全二叉樹更適合使用順序結(jié) 構(gòu)存儲(chǔ)?，F(xiàn)實(shí)中我們通常把堆(一種完全二叉樹)使用順序結(jié)構(gòu)的數(shù)組來(lái)存儲(chǔ)

堆的概念和結(jié)構(gòu)：

堆的性質(zhì)：

堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；

堆總是一棵完全二叉樹。

上面這些都是復(fù)制粘貼的， 想看了隨便看看。下面給出自己的一些總結(jié)：

C++實(shí)現(xiàn)堆

Heap.h

#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
#include<Windows.h>
using namespace std;
typedef int DataType;
class Heap
{
public:
	Heap() :a(new DataType[1]), size(0), capacity(1) {}
	~Heap()
	{
		delete[]a;
		a = nullptr;
		size = capacity = 0;
	}
public:
	void Push(const DataType& x);
	void Pop();    // 刪除堆頂?shù)臄?shù)據(jù)
	DataType Top()const;
	bool Empty()const;
	int Size()const;
	void Swap(DataType& a, DataType& b);
	void print();
public:
	void AdjustUp(int child);
	void AdjustDown(int size, int parent);
private:
	DataType* a;
	int size;
	int capacity;
};

Heap.cpp

#include"Heap.h"
void Heap::Swap(DataType& a, DataType& b)
{
	DataType tmp = a;
	a = b;
	b = tmp;
}
void Heap::Push(const DataType& x)
{
	if (size == capacity)
	{
		int newcapacity = capacity == 0 ? 1 : capacity * 2;
		DataType* tmp = new DataType[newcapacity];
		assert(tmp);
		std::copy(a, a + size, tmp);
		delete a;
		a = tmp;
		capacity = newcapacity;
	}
	a[size] = x;
	AdjustUp(size);
	++size;
}
void Heap::Pop() // 刪除堆頂?shù)臄?shù)據(jù)
{
	assert(size > 0);
	Swap(a[0], a[size - 1]);
	size--;
	AdjustDown(size, 0);
}
DataType Heap::Top()const
{
	assert(size > 0);
	return a[0];
}
bool Heap::Empty()const
{
	return size == 0;
}
int Heap::Size()const
{
	return size;
}
void Heap::AdjustUp(int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(a[parent], a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
	//int parent = (child - 1) / 2;
	//if(child > 0)
	//{
	//	if (a[parent] > a[child])
	//	{
	//		Swap(a[parent], a[child]);
	//		child = parent;
	//		AdjustUp(child);
	//	}
	//	else
	//	{
	//		return;
	//	}
	//}
}
void Heap::AdjustDown(int size,int parent) // size 是總大小，parent是從哪里開始向下調(diào)整 
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
			child++;
		if (a[child] < a[parent])
		{
			Swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void Heap::print()
{
	for (int i = 0; i < size; ++i)
	{
		cout << a[i] << ' ';
	}
	cout << endl;
}

其實(shí)Heap這個(gè)類 物理結(jié)構(gòu)就是一個(gè)一維數(shù)組，只是邏輯結(jié)構(gòu)是一個(gè)堆，我們將其想象成一個(gè)具有特定規(guī)律的完全二叉樹：特定規(guī)律就是任意一個(gè)二叉樹的根節(jié)點(diǎn)都>=或<=其子節(jié)點(diǎn)。

這個(gè)Heap類的關(guān)鍵是push和pop函數(shù)，與之相關(guān)的是向上調(diào)整和向下調(diào)整函數(shù)，這也是堆的精髓所在。

push是在數(shù)組尾部也就是堆的最下面插入一個(gè)元素，此時(shí)應(yīng)該調(diào)用向上調(diào)整算法，因?yàn)榇私Y(jié)點(diǎn)的插入可能破壞了原來(lái)的堆的結(jié)構(gòu)，因此，向上調(diào)整即可，但是有個(gè)前提，即插入此結(jié)點(diǎn)之前這個(gè)完全二叉樹本身符合堆的特性。并且調(diào)整只會(huì)影響此插入結(jié)點(diǎn)的祖宗，不會(huì)對(duì)其他節(jié)點(diǎn)產(chǎn)生影響。

pop是刪除堆頂?shù)脑?，且只能刪除堆頂?shù)脑兀驗(yàn)槎堰@個(gè)數(shù)據(jù)結(jié)構(gòu)的一個(gè)主要功能就是選數(shù)：即選出當(dāng)前堆中最大或者最小的數(shù)，并且選數(shù)的效率很高。pop刪除堆頂元素之后，再進(jìn)行一下調(diào)整即可選出次大或者次小的元素。

那么，怎么刪除呢？即將堆頂和末尾的數(shù)字交換，然后刪除交換后的末尾數(shù)字，此時(shí)堆頂元素很可能破壞了堆的結(jié)構(gòu)，因此采用向下調(diào)整的算法。向下調(diào)整算法有一個(gè)前提：左右子樹必須是一個(gè)堆，才能調(diào)整。

堆的應(yīng)用

向上調(diào)整算法和向下調(diào)整算法不僅僅用于Heap的插入和刪除操作，在堆排序等堆的應(yīng)用中也要使用。

堆排序

傳入一個(gè)數(shù)組，對(duì)數(shù)組進(jìn)行排序，且是一個(gè)O(N*LogN)的算法，效率很高。

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			swap(a[parent], a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(int* a,int size, int parent) // size 是總大小，parent是從哪里開始向下調(diào)整 
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
			child++;
		if (a[child] < a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

HeapSort

void HeapSort(int* a, int n)
{
	// 將傳入的數(shù)組看作一個(gè)完全二叉樹，然后調(diào)整為堆。
	// 升序調(diào)整為大根堆，降序小根堆。
	// 建堆方式1： O(N*LogN)
	// 利用向上調(diào)整算法,其實(shí)就是堆的插入函數(shù)
	//for (int i = 1; i < n; ++i)
	//{
	//	AdjustUp(a, i);
	//}
	// 建堆方式2： O(N)
	// 利用向下調(diào)整算法
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	// 建好堆之后排序 目前是一個(gè)小堆，小堆用來(lái)排降序
	// 5 13 17 19 22 27 32 35 38 42 45
    // O(N * LogN);
    int end = n - 1;
	while (end > 0)
	{
		swap(a[0], a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

前面說過，堆的一個(gè)主要或者說唯一作用就是選數(shù)，大根堆選出最大數(shù)，小根堆選出最小數(shù)，先將給定數(shù)組調(diào)整為堆，若排升序則調(diào)整為大根堆，此時(shí)a[0]即最大值，將其與數(shù)組末尾數(shù)組交換，然后進(jìn)行向下調(diào)整即可選出次大值，再進(jìn)行交換即可。整個(gè)邏輯十分像Heap類的刪除操作，只是將刪除了的堆頂元素放置在數(shù)組末尾而已，然后不斷進(jìn)行這個(gè)操作，直到整個(gè)數(shù)組有序。

將數(shù)組調(diào)整為堆的思路有兩個(gè)，一種是模擬插入的操作，從頭遍歷逐個(gè)將元素進(jìn)行向上調(diào)整操作，主要是因?yàn)橄蛏险{(diào)整算法必須基于此完全二叉樹本身就是一個(gè)堆，才可以進(jìn)行向上調(diào)整操作。所以從尾開始向上調(diào)整肯定是不行的。

思路二與思路一有相同之處，即利用向下調(diào)整算法，向下調(diào)整基于此結(jié)點(diǎn)的左子樹和右子樹都是堆，所以直接從頭開始向下調(diào)整不可以，所以從尾向前遍歷進(jìn)行向下調(diào)整，且末尾的葉子結(jié)點(diǎn)沒有必要調(diào)整，所以從第一個(gè)結(jié)點(diǎn)數(shù)>=2的二叉樹開始進(jìn)行向下調(diào)整。

HeapSort的邏輯不會(huì)受升序和降序的影響，只需要將AdjustUp和AdjustDown的調(diào)整邏輯改變即可。

為什么排升序要建大根堆，不建小根堆呢？

首先，如果建小根堆，確實(shí)建好之后的數(shù)組比較像升序，且此時(shí)最小值也已經(jīng)在數(shù)組的a[0]處，但是，選次大的元素時(shí)，對(duì)于后面a[1] 至 a[n-1]個(gè)元素，此時(shí)之前堆的兄弟父子關(guān)系全都亂了，向上調(diào)整和向下調(diào)整都不可以，只能重建堆，而重建堆的時(shí)間復(fù)雜度為O(N)。如此下去，每次挑出最大值都需要O(N)，最終的就是O(N)+O(N-1)+...+O(2)... 總的就是O(N^2)了。

而如果建大根堆，a[0]就是最大值，將其與數(shù)組末尾進(jìn)行交換，這個(gè)交換操作只是O(1)的操作，最重要的是交換之后，把末尾元素忽視之后的這個(gè)完全二叉樹，只有堆頂元素不符合堆，只需向下調(diào)整一次即可，為O(logN),即可選出次大值，相比于前面的O(N)就快了很多。

到此這篇關(guān)于C++超詳細(xì)實(shí)現(xiàn)堆和堆排序過像的文章就介紹到這了,更多相關(guān)C++堆和堆排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論