数据结构基础(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 <typename Type>
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 <typename Type>
MaxHeap<Type>::MaxHeap(int _maxSize)
    : maxSize(_maxSize),currentSize(0)
{
    if (maxSize < 1)
        throw std::length_error("heap size must >= 1");

    heapArray = new Type[maxSize];
}
//析构
template <typename Type>
MaxHeap<Type>::~MaxHeap()
{
    delete []heapArray;
    heapArray = NULL;
    currentSize = 0;
}
//判空
template <typename Type>
bool MaxHeap<Type>::isEmpty() const
{
    return currentSize == 0;
}

堆顶元素

//查看堆顶元素
template <typename Type>
const Type &MaxHeap<Type>::top() const
{
    if (isEmpty())
        throw std::underflow_error("heap is empty");

    return heapArray[0];
}

插入元素

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

    //维护堆的性质:向上渗透
    trickUp(currentSize);
    ++ currentSize;
}

//向上渗透, 将刚刚插入的元素移动到合适的位置上
template <typename Type>
void MaxHeap<Type>::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 <typename Type>
void MaxHeap<Type>::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 <typename Type>
void MaxHeap<Type>::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 <typename Type>
void MaxHeap<Type>::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 <typename Type>
void heapSort(Type *begin, Type *end)
{
    int size = end-begin;
    MaxHeap<Type> maxHeap(size);
    //存入堆中
    for (Type *current = begin; current < end; ++ current)
        maxHeap.push(*current);

    //从堆中取出
    while (begin != end)
    {
        *begin = maxHeap.top();
        ++ begin;
        maxHeap.pop();
    }
}

template <typename Type>
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;
}