最大堆和最小堆原理

系统中程序的运行、子线程的运行、以及一些其他的任务，是否都是按照一定的规律来先后执行，首先我们就会想到是按时间序列来完成。可是仔细一想，不可能任何的系统任务都是按时间序列来完成，比如关机和打开一个程序，系统总是会将关机安排在前一位，再比如说移动一个文件和系统的运行，这些都有明显的主次关系，不可能按时间序列来逐个运行，于是就有了最大/小堆（Heap）的概念。

一、堆的概念

了解一种数据结构，就先了解了解它的概念：堆（Heap)是计算机科学中一类特殊的数据结构的统称，堆通常是一个可以被看做一棵树的数组对象。而这棵树一定是一棵完全二叉树，而且如果他是最小树，则每个节点必定大于它的父节点，如果是最大树则所有父节点一定大于它的儿子节点，所以它的树根一定最大或者最小。比如形如这样的最大堆：

堆的实例

二、堆的 *** 作

知道了什么是堆之后我们就要学会用它，了解并知道编它的各种 *** 作，首先先来了解一下堆的结构，虽然上面说了堆是由二叉树的形式构成的，但是堆的结构其实和二叉树有区别，像上面说的“堆通常是一个可以被看做一棵树的数组对象”，所以它的结构就并不是左指针和右指针了，而是以数组的形式，而且为了方便后面的 *** 作（像插入、删除...），堆的结构中还有Size代表它当前的长度和Capacity代表它的总容量：

堆树的定义如下：

（1）堆树是一颗完全二叉树；

（2）堆树中某个节点的值总是不大于或不小于其孩子节点的值；

（3）堆树中每个节点的子树都是堆树。

当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。如下图所示，左边为最大堆，右边为最小堆。

二、堆树的 *** 作

以最大堆为例进行讲解，最小堆同理。

原始数据为a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}，采用顺序存储方式，对应的完全二叉树如下图所示：

（1）构造最大堆

在构造堆的基本思想就是：首先将每个叶子节点视为一个堆，再将每个叶子节点与其父节点一起构造成一个包含更多节点的对。

所以，在构造堆的时候，首先需要找到最后一个节点的父节点，从这个节点开始构造最大堆；直到该节点前面所有分支节点都处理完毕，这样最大堆就构造完毕了。

假设树的节点个数为n，以1为下标开始编号，直到n结束。对于节点i，其父节点为i/2；左孩子节点为i*2，右孩子节点为i*2+1。最后一个节点的下标为n，其父节点的下标为n/2。

如下图所示，最后一个节点为7，其父节点为16，从16这个节点开始构造最大堆；构造完毕之后，转移到下一个父节点2，直到所有父节点都构造完毕。

#include <iostream>

#include <vector>

using namespace std

#define Parent(i)  (((i) - 1) / 2)

#define Left(i)  (2 * (i) + 1)

#define Right(i) (2 * (i) + 2)

template<typename T>

void KeepHeap(vector<T>& Cont, size_t Index)

{

size_t Largest = Index

size_t Bound = Cont.size()

size_t left = Left(Index)

size_t right = Right(Index)

if (left <= Bound && Cont[left] > Cont[Index])

{

Largest = left

}

if (right <= Bound && Cont[right] > Cont[Largest])

{

Largest = right

}

if (Largest != Index)

{

T tmp = Cont[Largest]

Cont[Largest] = Cont[Index]

Cont[Index] = tmp

}

else

{

return

}

KeepHeap(Cont, Largest)

}

template<typename T>

void MakeHeap(vector<T>& Cont)

{

size_t Mid = Cont.size() / 2

for (int i = Mid - 1 i >= 0 --i)

{

KeepHeap(Cont, i)

}

}

写了个大概 能运行 但是肯定有纰漏 只是个玩具而已 不具有什么强度  LZ自己修改

不过复杂度应该是线性的 要证明复杂度为线性也是可以的

@heapsort

begin():

1.将数组转成堆 heapify()；

2.移出根结点的值，然后把最后一个元素移动到根节点处；

3.while(len>0)

调整堆 heapify()；

转2；

end()

堆化算法：最小堆

---