数据结构堆的代码实现


堆的数据结构,是什么呢?其实是一组完全二叉树。堆满足如下几个性质:

  1. 假如一个节点的索引是i(这里的索引从1开始),那么它的父节点的索引是⌊i/2⌋,左子节点的索引是 2i,右子节点的索引是 2i+1
  2. 父节点的值要么大于儿子节点,要么小于儿子节点。

当父节点大于儿子节点时,我们得到大堆,当父节点小于儿子节点时,我们得到小堆。我们现在以大堆举例。

大堆的实现源码如下:

#include <iostream>
#include <vector>

using namespace std;

void PrintHeap(vector<int> &array);

void Swap(vector<int> &array, int xpos, int ypos)
{
    //交换x和y处的元素值
    int temp = array[xpos];

    array[xpos] = array[ypos];
    array[ypos] = temp;
}

void Heapify(vector<int> & array, int size, int pos)
{
    //调整堆,让堆满足特性。即父节点的值要大于左右两个节点的值
    int left = 2*pos;
    int right = 2*pos+1;
    int maxpos = 0;

    if (left > size)
    {
        return ;
    }
    else if (right > size || array[left-1] > array[right-1])
    {
        maxpos = left;
    }
    else
    {
        maxpos = right;
    }
   
    //判断父节点与子节点的大小
    if (array[pos-1] >= array[maxpos-1])
    {
        return ;
    }

    //调整父子节点的值
    Swap(array, pos-1, maxpos-1);

    Heapify(array, size, maxpos);
}

void PrintHeap(vector<int> & array)
{
    int size = array.size();

    for(int i = 0; i < size; ++i)
    {
        cout<<array[i]<<",";
    }

    cout<<endl;
}

void PopHeap(vector<int> & array, int end)
{
    //堆的弹出。将根节点与尾节点互换
    Swap(array, 0, end-1);

    Heapify(array, end, 1);
}

void CreateHeap(vector<int> & array, int size)
{
    for(int i = size/2 ; i > 0; --i)
    {
        Heapify(array, size, i);
    }
}

void HeapUpify(vector<int> & array, int pos)
{
    //判断父节点的值
    if (pos == 0 || pos == 1)
    {
        return ;
    }

    int parpos = pos/2;

    if (array[parpos-1] < array[pos-1])
    {
        Swap(array, parpos - 1, pos - 1);

        //向上调整
        HeapUpify(array, parpos);
    }
}

void HeapInsert(vector<int> & array, int val)
{
    array.push_back(val);

    //开始判断大小端性质是否符合
    HeapUpify(array, array.size());  //维持堆的兴致
}

int main()
{
    int arr[10] = {4,1,3,2,16,9,10,14,8,7};
    vector<int> varr(arr, arr+10);

    CreateHeap(varr, 10);

    vector<int> vct(varr);

    PrintHeap(varr);

    PopHeap(varr, 10);

    PrintHeap(varr);

    PopHeap(varr, 9);
    
    PrintHeap(varr);

    HeapInsert(vct, 15); //往堆里插入新值

    PrintHeap(vct);

    HeapInsert(vct, 20);  
    HeapInsert(vct, 5);
    HeapInsert(vct, 6);

    PrintHeap(vct);

    return 0;
}
为了使数组可以任意扩展,所以代码中使用了vector集合。

Heapify()方法,通过使当前节点满足堆的特性。比较左右子节点中的较大值与自身值之间的大小。如果当前节点大,则本身就满足堆的特性,直接返回;反之,则调换当前节点与左右子节点中的较大值,并且向下继续传递这种比较。

HeapUpify()方法,则是将当前节点作为子节点,判断新插入的节点是否违背了堆的特性,即比较当前节点与父节点的值。如果比父节点小,说明满足堆的特性,直接返回;反之,如果比父节点大,说明违背了堆特性,则调换父节点与当前节点的值,并且将当前节点的索引值改为父节点的索引值,继续向上传递这种比较判断。



评论

发表评论