学习总结第三十二天——从树结构到堆排序

树结构，或者说树状结构，相信很多人都不陌生，它的名称来自于以树的象征来表现出构造之间的关系，虽然在图象的呈现上，其为一个上下颠倒的树。以下为维基中对于树结构的定义。

在计算机科学中，树（英语：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;
}