欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆(Heap)的实现

程序员文章站 2024-02-15 09:36:40
...

这次实现了堆,这个堆不是指系统堆栈的堆,是一种数据结构,见下图堆(Heap)的实现

堆的本质就是一个数组(上图中,红色的是值,黑色的是下标)简单的来说就是把一个数组看成是二叉树,就像上图

大堆和小堆分别是指根节点比孩子节点的值大或者是小,看了上图之后就可以发现,父亲节点和孩子节点之间下表的关系,parnet=(child-1)/2

利用这个关系就可以实现堆了,堆的基本方法有构造,析构,插入,删除,像大堆小堆这样特殊的堆肯定是要有调整函数来保持他们的特性的,所以我还写了向上调整和向下调整的函数

为了让大堆和小堆之间切换自如(就是方便维护),我写了两个仿函数,建立堆的对象时传个模版参数就好了

#pragma once
#include<iostream>
#include<vector>
using namespace std;

template<class T>
struct Less
{
    bool  operator()(const T& l,const T& r)
    {
        return l < r;
    }
};

template<class T>
struct Greater
{
    bool operator()(const T& l ,const T& r)
    {
        return l > r;
    }
};





template<class T, class Compare = Less<T>>
class Heap
{
public:
    Heap()
    {

    }
    Heap(vector<T> a)
        :array(a)
    {
        for (int i = (array.size() - 2) / 2; i >=0 ; --i)
        {
            AdjustDown(i);
        }
    }
    Heap(T *a, size_t size)
    {
        for (int i = 0; i < size; ++i)
        {
            array.push_back(a[i]);
        }
        for (int i = (array.size() - 2) / 2; i >= 0; --i)
        {
            AdjustDown(i);
        }
    }
    ~Heap()
    {
        
    }
    void Push(T x)
    {
        array.push_back(x);
        AdjustUp(array.size()-1);
    }
    void Pop()
    {
        swap(array.front(), array.back());
        array.pop_back();
        AdjustDown(0);
    }
    void AdjustDown(int root)
    {
        int child = root * 2 + 1;
        while (child < array.size())
        {
            if (child + 1 < array.size() && Compare()(array[child + 1], array[child]))
            {
                child++;
            }
            if (Compare(array[root], array[child]))
            {
                swap(array[root], array[child]);
                root = child;
                child = root * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
    void AdjustUp(int child)
    {
        int parent = (child - 1) / 2;
        while (child > 0)
        {
            if (Compare()(array[child], array[parent]))
            {
                swap(array[child], array[parent]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }
    }
    void Print()
    {
        for (int i = 0; i < array.size(); ++i)
        {
            cout << array[i] << " ";
        }
        cout << endl;
    }
    int Size()
    {
        return array.size();
    }
protected:
    vector<T> array;
};


void TestHeap()
{
    Heap<int> hp;
    int a[10] = { 5,3,6,2,1,7,8,9,4,0 };
    for (int i = 0; i < 10; ++i)
    {
        hp.Push(a[i]);
    }
    hp.Print();
}


当一个一个push插入的时候我们只需要把这个元素插入到数组的最后,然后顺着二叉树向上调整就可以了(只需要调整这一条线)

删除头元素(根节点)的时候,为了不破坏结构,我们选择先跟处于最后位置的元素交换,之后在末尾删除掉“根节点”,然后因为最大值(最小值)被换到了根节点,不符合小堆(大堆)的结构要求,只需要顺着这条路一直向下调整就可以了

我还写了一个构造函数接收的参数是一个vector,这是把整个vector调整成大堆(小堆),先找到最后一个元素的父亲节点,一直往前向下调整就可以了,因为这个父亲节点之前也肯定都是有孩子父亲节点