数据结构基础(19) --堆与堆排序-白红宇

完全二叉树

首先让我们回顾一下完全二叉树的两个性质:

性质1:具有n个结点的完全二叉树的深度为[logn](向下取整)+1。

性质2:若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：

(1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 [i/2](向下取整)的结点为其双亲结点；

(2) 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；

(3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。

数组与完全二叉树

从上图可以看出, 如果完全二叉树从上到下且从左至右进行从0至n-1进行编号，则对完全二叉树的性质需要修改如下:

(1) 若 i=0，则该结点是二叉树的根，无双亲，否则，编号为 [(i-1)/2](向下取整)的结点为其双亲结点；

(2) 若 2i+1>n，则该结点无左孩子，否则，编号为 2i+1 的结点为其左孩子结点；

(3) 若 2i+2>n，则该结点无右孩子结点，否则，编号为2i+2 的结点为其右孩子结点。

大顶堆与小顶堆

堆是满足下列性质的数列{r1, r2, …，rn}：

(小顶堆)

(大顶堆)

大顶堆的设计

template 
     
      class MaxHeap{public:    MaxHeap(int _maxSize = 10);    virtual ~MaxHeap();    bool isEmpty() const;    void push(const Type &item);    void pop();    const Type &top() const;private:    //将堆的容量增大两倍    void resize();    //向上渗透    void trickUp(int index);    //向下渗透    void trickDown(int index);private:    Type *heapArray;    int maxSize;    //currentSize有两个含义:    // 1.代表当前堆中已经存储的元素数    // 2.代表当前完全二叉树的第一个空位    int currentSize;};

大顶堆的实现

//构造template 
     
      MaxHeap
      
       ::MaxHeap(int _maxSize)    : maxSize(_maxSize),currentSize(0){    if (maxSize < 1)        throw std::length_error("heap size must >= 1");    heapArray = new Type[maxSize];}//析构template 
       
        MaxHeap
        
         ::~MaxHeap(){    delete []heapArray;    heapArray = NULL;    currentSize = 0;}//判空template 
         
          bool MaxHeap
          
           ::isEmpty() const{ return currentSize == 0;}

堆顶元素

//查看堆顶元素template 
     
      const Type &MaxHeap
      
       ::top() const{    if (isEmpty())        throw std::underflow_error("heap is empty");    return heapArray[0];}

插入元素

//插入template 
     
      void MaxHeap
      
       ::push(const Type &item){    //如果堆已满, 则需要对堆进行扩充    if (currentSize == maxSize)    {        resize();    }    //将元素插入到堆的第一个空位置上    heapArray[currentSize] = item;    //维护堆的性质:向上渗透    trickUp(currentSize);    ++ currentSize;}

//向上渗透, 将刚刚插入的元素移动到合适的位置上template 
     
      void MaxHeap
      
       ::trickUp(int index){    //根据完全二叉树的性质, 找到父节点    int parent = (index-1)/2;    Type bottom = heapArray[index];    //循环终止条件    // 1. index = 0 //bottom元素插入到根节点    // 2. heapArray[parent] >= bottom   //bottom插入到parent节点的一个子节点上    while ((index > 0) && (heapArray[parent] < bottom))    {        //父节点下移        heapArray[index] = heapArray[parent];        index = parent;        parent = (parent-1)/2;    }    //插入    heapArray[index] = bottom;}

//将堆的大小加倍template 
     
      void MaxHeap
      
       ::resize(){    int newSize = std::max(maxSize*2, 1);    Type *newHeap = new Type[newSize];    for (int i = 0; i < currentSize; ++i)    {        newHeap[i] = heapArray[i];    }    delete []heapArray;    heapArray = newHeap;    maxSize = newSize;}

删除堆顶元素

//删除template 
     
      void MaxHeap
      
       ::pop(){    if (isEmpty())        throw std::underflow_error("heap is empty");    //只有一个元素    if (currentSize == 1)    {        heapArray[0].~Type();        currentSize = 0;        return ;    }    //显示释放堆顶元素    heapArray[0].~Type();    //直接将最有一个元素放到堆顶,    //并且currentSize-1    heapArray[0] = heapArray[-- currentSize];    //此时如果破坏了堆的性质:向下渗透    trickDown(0);}

//向下渗透template 
     
      void MaxHeap
      
       ::trickDown(int index){    int largeChild;    Type top = heapArray[index];    // 只需到达完全二叉树的最后一层    // 的上一层即可    // 循环的终止条件:    // 1. index已经到达了最后一层(index >= currentSize/2 :找到了一个比较合适的位置)    // 2. 在堆的中间找到了一个合适的位置(top >= heapArray[largeChild])    while (index < currentSize/2)    {        int leftChild = (index*2)+1;        int rightChild = leftChild + 1;        //如果有右儿子节点, 而且右儿子节点还大于左儿子节点        if (rightChild < currentSize && heapArray[rightChild] > heapArray[leftChild])            largeChild = rightChild;        else            largeChild = leftChild;        if (top >= heapArray[largeChild])            break;        //不然的话, 则需继续向下渗透        heapArray[index] = heapArray[largeChild];        // index需要向下搜索        index = largeChild;    }    //插入    heapArray[index] = top;}

堆排序

堆排序就是将元素一个一个插入到堆中, 然后再一个一个的取出来;

//堆排序template 
     
      void heapSort(Type *begin, Type *end){    int size = end-begin;    MaxHeap
      
        maxHeap(size);    //存入堆中    for (Type *current = begin; current < end; ++ current)        maxHeap.push(*current);    //从堆中取出    while (begin != end)    {        *begin = maxHeap.top();        ++ begin;        maxHeap.pop();    }}template 
       
        void heapSort(Type *array, int arraySize){    return heapSort(array, array+arraySize);}

附-测试代码:

int main(){    int array[20];    for (int i = 0; i < 20; ++i)    {        array[i] = rand()%100;        cout << array[i] << ' ';    }    heapSort(array, 20);    cout << endl;    for (int i = 0; i < 20; ++i)    {        cout << array[i] << ' ';    }    cout << endl;    return 0;}