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

堆---实现最小堆及堆的插入与删除

程序员文章站 2022-03-31 19:08:30
...


优先级队列的各种实现中,是最高效的一种数据结构
假定在各个数据记录(或元素)中存在一个能够标识数据记录(或元素)的数据项,并将依据该数据项对数据进行组织,则可数据项成为关键码(key)
如果有一个关键码的集合K = {k0 , k1 , k2 , … , kn-1},把它的所有元素按完全二叉树的顺序存储存放在一个一维数组中。并且满足:

ki <= k2i+1 且 ki <= k2i+2 或者(ki >= k2i+1 且 ki >= k2i+2)i = 0 , 1 , … , [(n - 2) / 2]

则称这个集合为最小堆(或最大堆

堆---实现最小堆及堆的插入与删除

由于堆存储在下标从0开始计数的数组中,因此,在堆中给定下标为i的结点时:

  1. 如果 i = 0,结点 i 是根结点,无父结点;否则结点 i 的父结点为结点 [(i - 2) / 2]
  2. 如果 2i + 1 > n - 1,则结点 i 无左子女;否则结点 i 的左子女为结点 2i + 1
  3. 如果 2i + 2 > n - 1,则结点 i 无右结点;否则结点 i 的右子女为结点 2i + 2

实现最小堆

第一步:建堆
利用给定的数组大小和数组元素,创建堆空间,并进行拷贝。
第二步:调整成为最小堆
利用自定义的siftDown()函数,实现下滑调整。
堆---实现最小堆及堆的插入与删除

插入与删除

插入
堆---实现最小堆及堆的插入与删除

删除
由于堆是队列结构,只能从堆中删除堆顶元素。移除堆顶元素之后,用堆的最后一个节点填补取走的堆顶元素,并将堆的实际元素个数减1。但用最后一个元素取代堆顶元素之后有可能破坏堆,因此需要将对自顶向下调整,使其满足最大或最小堆。
堆---实现最小堆及堆的插入与删除
代码实现

#include<iostream>
using namespace std;


template<class T>
class Heap
{
public:
    //构造函数
    Heap()
    :haep(NULL)
    {}

    //构造函数
    Heap(T * arr, int sz)
    {
        HeapSize = (DefaultSize < sz) ? sz : DefaultSize;
        heap = new T[HeapSize];
        heap = arr;
        if (heap == NULL)
            cout << "内存分配失败!" << endl;
        for (int i = 0; i < sz; i++)
            heap[i] = arr[i];
        currentSize = sz;
    }

    //调整为小堆
    void MinHeap()
    {
        currentPos = (currentSize - 2) / 2;//最初调整位置:最后分支点
        while (currentPos >= 0)
        {
            siftDown(currentPos, currentSize-1);
            currentPos--;
        }

    }

    //向堆插入新元素
    bool Insert(T x)
    {
        if (currentSize == HeapSize)
        {
            cerr << "Heap Full" << endl;
            return false;
        }

        heap[currentSize] = x;
        siftUp(currentSize);
        currentSize++;
        return true;

    }

private:
    T * heap;//存放堆的数组
    int DefaultSize = 10;//默认堆的大小
    int HeapSize;//当前堆的大小
    int currentSize;//最小堆中当前元素个数
    int currentPos;//最初调整位置

    //从start到m下滑调整成为最小堆
    void siftDown(int start, int m)
    {
        int i = start;
        int j = 2 * i + 1;
        T temp = heap[i];
        while (j <= m)
        {
            if (j < m && heap[j] > heap[j + 1])
                j = j + 1;

            if (temp <= heap[j])
                break;
            else
            {
                heap[i] = heap[j];
                i = j;
                j = 2 * j + 1;
            }   
        }
        heap[i] = temp;
    }

    //从start到0上滑调整成为最小堆
    void siftUp(int start)
    {
        int j = start;
        int i = (start - 1) / 2;
        T temp = heap[j];
        while (j > 0)
        {           
            if (heap[i] >= temp)
            {
                heap[j] = heap[i];
                j = i;
                i = (i - 1) / 2;
            }
        }
        heap[j] = temp;
    }
};



int main()
{
    int arr[6] = { 5, 4, 3, 2, 1, 0 };
    Heap<int> s(arr, 6);
    s.MinHeap();
    s.Insert(-1);
    for (int i = 0; i < 6; i++)
        cout << arr[i] << " ";
    return 0;


}