堆（Heap）的实现

堆（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调整成大堆（小堆），先找到最后一个元素的父亲节点，一直往前向下调整就可以了，因为这个父亲节点之前也肯定都是有孩子父亲节点

本文永久更新链接地址：