C++超詳細實現堆和堆排序過像

#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();    // 刪除堆頂的資料
	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;
};

#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() // 刪除堆頂的資料
{
	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是從哪裡開始向下調整 
{
	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;
}

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是從哪裡開始向下調整 
{
	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 HeapSort(int* a, int n)
{
	// 將傳入的陣列看作一個完全二元樹，然後調整為堆。
	// 升序調整為大根堆，降序小根堆。
	// 建堆方式1： O(N*LogN)
	// 利用向上調整演演算法,其實就是堆的插入函數
	//for (int i = 1; i < n; ++i)
	//{
	//	AdjustUp(a, i);
	//}
	// 建堆方式2： O(N)
	// 利用向下調整演演算法
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, 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--;
	}
}