什么是堆

2018-06-17

堆(heap)

堆是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
堆的性质：
1.堆中某个节点的值总是不大于或不小于其父节点的值。
2.堆总是一棵完全二叉树。

堆的分类

将根节点最大的堆叫做最大堆或大顶堆，根节点最小的堆叫做最小堆或小顶堆。常见的堆有二叉堆、斐波那契堆等。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
大堆：
网络故障
小堆：

堆的操作

build:建立一个空堆；
insert:向堆中插入一个新元素；
update：将新元素提升使其符合堆的性质；
get：获取当前堆顶元素的值；
delete：删除堆顶元素；
heapify：使删除堆顶元素的堆再次成为堆。
某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。

建堆效率

n个结点的堆，高度d =log2n。根为第0层，则第i层结点个数为2i，考虑一个元素在堆中向下移动的距离。大约一半的结点深度为d-1，不移动（叶）。四分之一的结点深度为d-2，而它们至多能向下移动一层。树中每向上一层，结点的数目为前一层的一半，而子树高度加一。
这种算法时间代价为Ο（n)由于堆有log n层深，插入结点、删除普通元素和删除最小元素的平均时间代价和时间复杂度都是Ο（log n）。

关于堆的操作实现

在程序中，堆用于动态分配和释放程序所使用的对象。在以下情况中调用堆操作：
1.事先不知道程序所需对象的数量和大小。
2.对象太大，不适合使用堆栈分配器。
堆使用运行期间分配给代码和堆栈以外的部分内存。
传统上，操作系统和运行时库随附了堆实现。当进程开始时，操作系统创建称为进程堆的默认堆。如果没有使用其他堆，则使用进程堆分配块。语言运行时库也可在一个进程内创建单独的堆。（例如，C 运行时库创建自己的堆。）除这些专用堆外，应用程序或许多加载的动态链接库 (DLL) 之一也可以创建并使用单独的堆。Win32 提供了一组丰富的 API用于创建和使用专用堆。有关堆函数的优秀教程，请参阅 MSDN 平台 SDK 节点。
当应用程序或 DLL 创建专用堆时，这些堆驻留于进程空间中并且在进程范围内是可访问的。某一给定堆分配的任何数据应为同一堆所释放。（从一个堆分配并释放给另一个堆没有意义。）
在所有虚拟内存系统中，堆位于操作系统的虚拟内存管理器之上。语言运行时堆也驻留在虚拟内存之上。某些情况下，这些堆在操作系统堆的上层，但语言运行时堆通过分配大的块来执行自己的内存管理。绕开操作系统堆来使用虚拟内存函数可使堆更好地分配和使用块。
典型的堆实现由前端分配器和后端分配器组成。前端分配器维护固定大小块的自由列表。当堆收到分配调用后，它尝试从前端列表中查找自由块。如果此操作失败，则堆将被迫从后端（保留和提交虚拟内存）分配一个大块来满足请求。通常的实现具有每个块分配的开销，这花费了执行周期，也减少了可用存储区。
单个全局锁可防止多线程同时使用堆。此锁主要用于保护堆数据结构不受多线程的任意访问。当堆操作过于频繁时，此锁会对性能造成负面影响。

代码实现

#pragma once
template<class T>

class JBMinHeap
{
private:
    //申请堆空间
    T *_minHeap = NULL;
    int _index,_maxSize;
public:
    JBMinHeap(int maxSize) {
        _maxSize = maxSize;
        _minHeap = new T[_maxSize];
        _index = -1;
    }
    JBMinHeap(JBMinHeap &h) {
        _index = h._index;
        _maxSize = h._maxSize;
        _minHeap = new T[_maxSize];
        for (int i = 0;i<_maxSize) {
            *_minHeap[i] = *h._minHeap[i];
        }
    }
    ~JBMinHeap() {
        delete[]_minHeap;
    }
    //获取整个最小堆的头部指针
    T * getMinHeap() {
        return _minHeap;
    }
    //判断堆是不是空的
    bool isEmpty() {
        return _index == -1;
    }
    bool add(T x) {
        if (isFull()) {
            return false;
        }
        _index++;
        _minHeap[_index] = x;
        return true;
    }
    bool isFull() {
        return _index == _maxSize;
    }
    //堆进行向下调整
    void adjustDown(int index);
    //队进行向上调整
    void adjustUp(int index);
    //建堆运算
    void createMinHeap() {
        if (isEmpty()) {
            return;
        }
        for (int i = (_index-1)/2;i >-1;i--) {//直接从倒数第二层 逐层向下调整
            adjustDown(i);
        }
    }
};

template<class T>
void JBMinHeap<T>::adjustDown(int index) {
    if (isEmpty()) {
        return;
    }
    while (index<_index)
    {
        T temp = _minHeap[index];//将当前索引的位置的值保存下来
        int oneC = 2 * index + 1;//获取到两个孩子的位置
        int twoC = 2 * index + 2;
        if (oneC == _index) {//若第一个孩子是整个堆最后一个位置 则直接执行交换操作并结束执行
                _minHeap[index] = _minHeap[oneC];
                _minHeap[oneC] = temp;
                return;
        }
        if (twoC >_index) {//如果第二个孩子的索引位置越界 结束执行
            return;
        }
        if (_minHeap[oneC] <= _minHeap[twoC]) {//正常情况的数据交互执行
            if (temp > _minHeap[oneC]) {
                _minHeap[index] = _minHeap[oneC];
                _minHeap[oneC] = temp;
                index = oneC;
            }
            else {//如果该处索引值已经是比两个孩子小 则结束循环
                index = _index;
            }
        }
        else
        {
            if (temp > _minHeap[twoC]) {
                _minHeap[index] = _minHeap[twoC];
                _minHeap[twoC] = temp;
                index = twoC;
            }
            else
            {
                index = _index;
            }
        }
    }
}

template<class T>
void JBMinHeap<T>::adjustUp(int index) {
    if (index > _index) {//大于堆的最大值直接return
        return;
    }
    while (index>-1)
    {
        T temp = _minHeap[index];
        int father = (index - 1) / 2;
        if (father >= 0) {//若果索引没有出界就执行想要的操作
            if (temp < _minHeap[father]) {
                _minHeap[index] = _minHeap[father];
                _minHeap[father] = temp;
                index=father;
            }
            else {//若果已经是比父亲大 则直接结束循环
                index = -1;
            }
        }
        else//出界就结束循环
        {
            index = -1;
        }
    }
}

本文总阅读量次