[数据结构与算法]cpp 堆/堆排序

https://www.cnblogs.com/jingmoxukong/p/4303826.html
首先应该先了解堆的基础知识。
再向下调整或者向上调整时，要明确的几个点。
设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2i+1];
(2) 它的右孩子结点是：R[2i+2];
(3) 它的父结点是：R[(i-1)/2];
本质是对一颗完全二叉树的操作。

#pragma once
#include <iostream>
#include <vector>
using namespace std;
class BigHeap
{
public:
	bool operator()()
	{
		return true;
	}
};
class SmallHeap
{
public:
	bool operator()()
	{
		return true;
	}
};

template<class T, class BigOrSmall>
class Heap
{
public:
	std::vector<T> array_;
	BigOrSmall big_heap_;
	Heap(int* arr, size_t size)
	{
		for (int i = 0; i < size; i++)
		{
			array_.push_back(arr[i]);
		}
		//自底向上，构建堆，向上调整
		for (int i = (array_.size() - 2) / 2; i >= 0; i--)
		{
			AdjustDown(i);
		}
		cout << endl;
		for (int i = 0; i < size; i++)
		{
			cout << array_[i] << " ";
		}
	}
	void Push(T data)
	{
		array_.push_back(T);
		AdjustUp(array_.size() - 1);

	}
	T Pop()
	{
		swap(array_[0], array_[array_.size() - 1]);
		T tmp = array_[array_.size() - 1];
		array_.pop_back();
		AdjustDown(0);
		cout << endl;
		return tmp;
	}
	void HeapSort()
	{
		int i = 0;
		if (big_heap_())
		{
			while (i < array_.size() - 1)
			{
				if (array_[i] < array_[i + 1])
					swap(array_[i], array_[i+1]);
				AdjustDown(i);
				++i;
			}
		}
		else
		{
			while (i < array_.size() - 1)
			{
				if (array_[i] > array_[i + 1])
					swap(array_[i], array_[i + 1]);
				AdjustDown(i);
				++i;
			}
		}
	}
protected:
	
	void AdjustDown(size_t index)
	{
		while (index < array_.size() - 1)
		{
			//大根堆，array[0]为最大值
			if (big_heap_())
			{
				//调整左右孩子,使得右边孩子大于左孩子
				if ((index * 2 + 2) < array_.size() && array_[index * 2 + 1] < array_[index * 2 + 2])
				{
					swap(array_[index * 2 + 2], array_[index * 2 + 1]);
				}
				//调整父子，使得父节点大于左孩子
				if ((index * 2 + 1) < array_.size() && array_[index * 2 + 1] > array_[index])
				{
					swap(array_[index], array_[index * 2 + 1]);
				}

			}
			//小根堆
			else
			{
				//调整左右孩子,使得右边孩子小于左孩子
				if ((index * 2 + 2) < array_.size() - 2 && array_[index * 2 + 1] > array_[index * 2 + 2])
				{
					swap(array_[index * 2 + 2], array_[index * 2 + 1]);
				}
				//调整父子，使得父节点小于左孩子
				if ((index * 2 + 1) < array_.size() - 2 && array_[index * 2 + 1] < array_[index])
				{
					swap(array_[index], array_[index * 2 + 1]);
				}
			}
			index = index * 2 + 1;
		}
	}
	void AdjustUp(size_t index)
	{
		while (index != 0)
		{
			size_t i = (index - 1) / 2;
			//仿函数
			if (big_heap_())
			{
				if (index + 1 < array_.size() && array_[index + 1] > array_[index])
					swap(array_[index + 1], array_[index]);
				if (array_[i] < array_[index])
					swap(array_[index], array_[i]);
				else
					break;//当前节点已经大于了子节点不用再调整堆了
			}
			else
			{
				if (index + 1 < array_.size() && array_[index + 1] < array_[index])
					swap(array_[index + 1], array_[index]);
				if (array_[i] > array_[index])
					swap(array_[index], array_[i]);
				else
					break;
			}
			index = i;
		}
	}

	
private:
	Heap() {}
};