树结构，或者说树状结构，相信很多人都不陌生，它的名称来自于以树的象征来表现出构造之间的关系，虽然在图象的呈现上，其为一个上下颠倒的树。以下为维基中对于树结构的定义。
在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 树的度：一棵树中，最大的节点的度称为树的度；
- 叶节点或终端节点：度为零的节点；
- 非终端节点或分支节点：度不为零的节点；
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
- 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
- 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m（m>=0）棵互不相交的树的集合称为森林；
而每个节点最多含有两个子树的树又被称为二叉树，下图为一颗二叉树的结构
明白了二叉树以后，我们便可以来实现一种特殊的二叉树——“二叉堆”。
想象一下我们堆东西时的情景，大的物体堆在下层，小的堆在上层。二叉堆同理，父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆，相反，当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。
二叉堆一般采用数组来实现，并且舍弃了下标为0的值，这样的话便可以满足关系：元素i的子节点为2i和2i+1。可以方便的遍历一个二叉堆。同时我们应该实现两个方法，让二叉堆在从堆顶移除元素和在堆底添加元素后，能够恢复二叉堆原来的性质。
我们一般将这两个方法命名为sink()和swim()，这个过程可以看作，减少一个元素，就要让最后的元素补上开头的位置，再让这个元素下沉(sink)到合适的位置，增加一个元素，就要在堆的最后插入元素，再将这个元素上浮(swim)到合适的位置。
利用我们所实现二叉堆的两个方法，我们可以实现一个优先队列，有限队列与队列有些像，但是其返回值永远为队列中的最大/最小值。目前已知的有限队列的实现方法中，二叉堆是最实用的，因为其将入列和出列操作都限制在O(nlgn)的时间复杂度之内。
以下为一个返回最大值的优先队列实现：
template <typename T>void swap(T &a, T&b)
{
T temp = a;
a = b;
b = temp;
}
template <typename T>class MaxPQ
{
private:
T *datas;
int pqsize;
int pqcount;
void swim(int k);
void sink(int k);
public:
MaxPQ ();
MaxPQ (int max);
MaxPQ (T d[], int size);
void insert(T v);
T max();
T delmax();
bool isEmpty();
int size();
void resize(int size);
virtual ~MaxPQ ();
};
template <typename T>void MaxPQ<T>::swim(int k)
{
while (k > 1 && this->datas[k>>1] < this->datas[k])
{
swap(this->datas[k>>1],this->datas[k]);
k>>=1;
}
}
template <typename T>void MaxPQ<T>::sink(int k)
{
while (k<<1 <= this->pqcount)
{
int j = k<<1;
if (j < this->pqcount && this->datas[j+1] > this->datas[j])
{
j++;
}
if (this->datas[j] > this->datas[k])
{
swap(this->datas[j],this->datas[k]);
}
k = j;
}
}
template <typename T>MaxPQ<T>::MaxPQ():pqsize(4),pqcount(0)
{
this->datas = new T[pqsize];
}
template <typename T>MaxPQ<T>::MaxPQ(int max):pqsize(max),pqcount(0)
{
this->datas = new T[pqsize];
}
template <typename T>MaxPQ<T>::MaxPQ(T d[], int size):pqsize(size+1),pqcount(0)
{
this->datas = new T[pqsize];
for (int i = 0;i < size;i++)
{
this->insert(d[i]);
}
}
template <typename T>T MaxPQ<T>::max()
{
if (this->pqcount > 0)
{
return this->datas[1];
}
return (T)NULL;
}
template <typename T>T MaxPQ<T>::delmax()
{
if (this->pqcount > 0)
{
T max = this->datas[1];
//this->pqcount--;
if (this->pqcount > 0)
{
this->datas[1] = this->datas[pqcount];
this->pqcount--;
sink(1);
}
return max;
}
return (T)NULL;
}
template <typename T>bool MaxPQ<T>::isEmpty()
{
return this->pqcount == 0;
}
template <typename T>int MaxPQ<T>::size()
{
return this->pqcount;
}
template <typename T>void MaxPQ<T>::resize(int size)
{
T *new_data = new T[size];
for (int i = 0;i <= this->pqcount;i++)
{
new_data[i] = this->datas[i];
}
delete this->datas;
this->datas = new_data;
}
template <typename T>void MaxPQ<T>::insert(T v)
{
if (this->pqcount+1 >= this->pqsize)
{
pqsize <<= 1;
this->resize(pqsize);
}
this->datas[++this->pqcount] = v;
this->swim(this->pqcount);
}
template <typename T>MaxPQ<T>::~MaxPQ()
{
delete this->datas;
}
int main(int argc, char const *argv[])
{
MaxPQ<int> a;
//int input_value;
a.insert(3);
a.insert(3);
a.insert(234);
a.insert(2341);
a.insert(9999);
std::cout << a.delmax() << ' ' << a.delmax() << std::endl;
std::cout << a.delmax() << ' ' << a.delmax() << std::endl;
std::cout << a.delmax() << std::endl;
return 0;
}
堆排序，在实现了优先队列的基础上，就并不难了，只要数组先构建为有限队列，然后在依次执行出列操作，得到的一组数据就已经排序，同时我们还可以进一步简化，只用sink()方法就可以来构建一个堆，下面是一个堆排序的实现：
#include <iostream>
template <typename T>void sink(T *datas,int index,int size)
{
T new_node = datas[index];
while (index<<1 <= size)
{
int j = index<<1;
if (j < size && datas[j] < datas[j+1])
{
j++;
}
if (new_node > datas[j])
{
break;
}
datas[index] = datas[j];
index = j;
}
datas[index] =new_node;
}
template <typename T>void heap_sort(T datas, int size)
{
//构造二叉堆
for (int k = size<<1;k>0;k--)
{
sink(datas, k, size);
}
//排序
while(size > 1)
{
std::swap(datas[1],datas[size--]);//取出最大值
sink(datas, 1, size);//重新构造二叉堆
}
}
int main(int argc, char const *argv[])
{
int a[5] = {0,1,3,4,1};
heap_sort(a,5);
for (auto i:a)
{
std::cout << i << std::endl;
}
return 0;
}
