資料結構——堆

1.堆的概念

1、堆是一顆完全二叉樹（適合使用順序結構存盤）；

2、堆中的某個結點的值總是大于等于（最大堆）或小于等于（最小堆）其孩子結點的值，

3、堆中每個結點的子樹都是堆樹，

2.堆的實作

2.1堆的向下調整演算法

我們給出一個陣列，邏輯上看做一顆完全二叉樹，我們通過從根節點開始的向下調整演算法可以把它調整成一個小堆(大堆也可以，這里用小堆舉例)，向下調整演算法有一個前提：左右子樹必須是一個堆，才能調整，

void Swap(HPDataType* p, HPDataType* q)
{
	HPDataType temp = *p;
	*p = *q;
	*q = temp;
}
//前提：左右子樹都是小堆
void AdjustDown(HPDataType* a, int n, int root)
{
	//找出左右孩子出小的一個
	int parent = root;
	int child = parent * 2 + 1;//左孩子

	while (child < n)
	{
		//找出左右孩子中小的一個
		if ((child + 1 < n) && a[child + 1] < a[child])
		{
			child = child + 1;
		}

		//如果孩子小于父親就交換
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;//繼續下調
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
	
}

2.2堆的構建

堆的資料結構如下：

typedef int HPDataType;
typedef struct Heap
{ 
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

2.2.1構造最小堆

基本思想：首先將每個葉子結點視為一個堆，再將每個葉子結點于其父節點一起構成一個包含更多結點的堆，所以在構造堆的時候，首先需要找到最后一個結點的父節點，從這個節點開始構造小堆，直到該節點前面的所有分支節點都處理完畢，

設當前元素在陣列中以R[i]表示，那么:
1.它的左孩子結點是：R[2i+1];
2.它的右孩子結點是: R[2i+2];
3. 它的父結點是：R[(i-1)/2];

堆的初始化：

//初始化
void HeapInit(Heap* php, HPDataType* arr, int n)
{
	php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	memcpy(php->_a, arr, sizeof(HPDataType) * n);
	php->_size = n;
	php->_capacity = n;

	//構建堆
	//i是從最后一個非葉子結點的索引開始的
	for (int i = (n-1-1) / 2; i >= 0; i--)
	{
		AdjustDown(php->_a, n, i);//下調
	}
}

2.2.2時間復雜度分析：

第一層節點的個數為2^0個，單個節點向下調整的次數為h-1次
第二層的節點個數為2^1個，單個節點向下調整的次數為h-2次
第三層的節點個數為2^2個，單個節點的向下調整次數為h-3次
…
第h-1層的節點個數為2^(h-2)個，每個節點的向下調整次數為1次

即可求出：時間復雜度=2^0 * h-1+2^1 * (h-2)+2^2 * (h-3)+…+2^(h-2) * 1

通過h=logN和錯位相減得到：時間復雜度=N-logN

即建堆的時間復雜度為：O(N)

2.3堆的插入

堆的插入是在最后一個位置插入，就是陣列的尾插，然后在進行向上調整，

//向上調整
void AdjustUp(HPDataType* a, int n, int child)
{
	int parent = (child - 1) / 2;//父親結點

	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//插入
void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	//如果空間不夠增容
	if (php->_size == php->_capacity)
	{
		php->_capacity *= 2;
		HPDataType* temp = (HPDataType*)realloc(php->_a, sizeof(HPDataType) * php->_capacity);

		php->_a = temp;
	}

	php->_a[php->_size++] = x;//賦值，size+1

	AdjustUp(php->_a, php->_size, php->_size - 1);//傳入
}

2.4 堆的洗掉，取堆頂元素，取堆的資料個數，堆的判空

堆的洗掉是刪頭

//刪頭
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->_size > 0);

	Swap(&php->_a[0], &php->_a[php->_size - 1]);
	php->_size--;

	AdjustDown(php->_a, php->_size, 0);
}

//取堆頂的元素
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->_size > 0);

	return php->_a[0];
}

// 堆的資料個數
int HeapSize(Heap* php)
{
	assert(php);
	return php->_size;
}

// 堆的判空 1為空，0為非空
int HeapEmpty(Heap* php)
{
	assert(php);
	return php->_size == 0 ? 1 : 0;
}

3.堆排序

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序演算法，
堆是一個近似完全二叉樹的結構，并同時滿足堆積的性質：
即子結點的鍵值或索引總是小于（或者大于）它的父節點，
堆排序的平均時間復雜度為 Ο(nlogn)

3.1 （小堆）降序

排降序用小堆

void HeapSort(int* a, int n)
{
	//1.排降序建小堆   2.排升序建大堆

	//1.建堆,i為每個小堆的root
	//時間復雜度O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	
	//2.堆頂元素和最后一個元素互換，在對end-1個元素下調
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);//首尾互換，把最小的放到最后

		//再繼續選次小的
		AdjustDown(a, end, 0);
		--end;
	}
}