Heap

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆就是用数组实现的二叉树，所有它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。

堆的常用方法

  • 构建优先队列
  • 支持堆排序
  • 快速找出一个集合中的最小值（或者最大值）

堆属性

堆分为两种：最大堆和最小堆，两者的差别在于节点的排序方式。
在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。

堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。

  • 节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。
  • 内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来村塾数组，且不使用指针。
  • 平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log⁡n)O(\log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log⁡n)O(\log n) 的性能。
  • 搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

最大堆代码实现(代码来源)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1005;

const int MaxData = INF;
const int MaxSize = maxn;
typedef int ElementType;
typedef struct HeapStruct *MaxHeap;
MaxHeap Create(int MaxSize);
bool IsFull(MaxHeap H);
void Insert(MaxHeap H, ElementType item);
bool IsEmpty(MaxHeap H);
ElementType DeleteMax(MaxHeap H);

/*************************************************************************
最大堆的储存，其实用一个数组进行，这里的指针等价
************************************************************************/
struct HeapStruct
{
    ElementType *Elements;//heap array
    int Size;
    int Capacity;//最大容量
};

class __MaxHeap
{
public:
    MaxHeap ele;
    /*************************************************************************
    创建一个堆
     ************************************************************************/
    MaxHeap Create(int MaxSize)
    {
        MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct));
        H->Elements = (ElementType*)malloc((MaxSize + 1) * sizeof(ElementType));
        H->Size = 0;
        H->Capacity = MaxSize;
        H->Elements[0] = MaxData;//哨兵，大于堆中所有可能元素
        return H;
    }
    /*************************************************************************

     ************************************************************************/
    void Insert(MaxHeap H, ElementType item)
    {
        int i;
        if (IsFull(H))
        {
            printf("最大堆已满\n");
            return;
        }
        i = ++H->Size;
        for (; H->Elements[i / 2] < item; i /= 2)
            H->Elements[i] = H->Elements[i / 2];
        H->Elements[i] = item;
    }
    /*************************************************************************

     ************************************************************************/
    ElementType DeleteMax(MaxHeap H)
    {
        int Parent, Child;
        ElementType MaxItem, temp;
        if (IsEmpty(H))
        {
            printf("最大堆空\n");
            return -1;
        }
        MaxItem = H->Elements[1];
        temp = H->Elements[H->Size--];
        for (Parent = 1; Parent * 2 <= H->Size; Parent = Child)
        {
            Child = Parent * 2;
            if ((Child != H->Size) && (H->Elements[Child] < H->Elements[Child + 1]))
                Child++;
            if (temp >= H->Elements[Child])
                break;
            else
                H->Elements[Parent] = H->Elements[Child];
        }
        H->Elements[Parent] = temp;
        return MaxItem;
    }
    /*************************************************************************

     ************************************************************************/
    bool IsFull(MaxHeap H)
    {
        return (H->Size == H->Capacity);
    }
    /*************************************************************************

     ************************************************************************/
    bool IsEmpty(MaxHeap H)
    {
        return (H->Size == 0);
    }

    /*************************************************************************

     ************************************************************************/
    void Print(MaxHeap H)
    {
        int co = 2;
        for (int i = 1; i <= H->Size; i++)
        {
            i > co - 1?puts(""),co <<= 1:i;
            printf("%d ", H->Elements[i]);
        }
        puts("\n");
        return;
    }
};

/*************************************************************************

 ************************************************************************/
int main()
{
    __MaxHeap H;
    H.ele = H.Create(MaxSize);
    H.Insert(H.ele, 5);
    H.Insert(H.ele, 4);
    H.Insert(H.ele, 10);
    H.Insert(H.ele, 8);
    H.Insert(H.ele, 7);
    H.Insert(H.ele, 9);
    H.Insert(H.ele, 6);
    H.Print(H.ele);
    H.DeleteMax(H.ele);
    H.Print(H.ele);
    H.DeleteMax(H.ele);
    H.Print(H.ele);
    H.DeleteMax(H.ele);
    H.Print(H.ele);
    H.DeleteMax(H.ele);
    H.Print(H.ele);
    H.DeleteMax(H.ele);
    H.Print(H.ele);
    H.DeleteMax(H.ele);
    H.Print(H.ele);
    H.DeleteMax(H.ele);
    H.Print(H.ele);
    H.DeleteMax(H.ele);
    H.Print(H.ele);
    return 0;
}


stl优先队列+最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 10000
//priority_queue
int heap[MAX_N],sz = 0;
void push(int x)
{
    int i = sz++;
    while(i > 0)
    {
        int p = (i - 1) / 2;													//p 为父节点编号
        if(heap[p] <= x)
            break;													//父子节点没有大小颠倒则退出
        heap[i] = heap[p];														//父子互换
        i = p;
    }
    heap[i] = x;
}

int pop()
{
    int ret = heap[0];															//*min_element() 返回值
    int x = heap[--sz];															//最后一个数提到根
    int i = 0;
    while(i * 2 + 1 < sz)														//从根开始向下交换，
    {
        int a = i * 2 + 1,b = i * 2 + 2;										//取出较小的子节点
        if(b < sz && heap[b] < heap[a] )
            a = b;
        if(heap[a] >= x)														//父子节点大小颠倒则退出
            break;
        heap[i] = heap[a];														//
        i = a;

    }
    heap[i] = x;
    return ret;
}

int main()
{
    push(10);
    push(1);
    push(2);
    cout<<pop()<<endl;
    cout<<heap[0]<<endl;
    //stl优先队列
    priority_queue<int> q;
    q.push(10);
    q.push(1);
    q.push(2);
    cout<<q.top()<<endl;
    q.pop();
    cout<<q.top()<<endl;
//	system("pause");
    return 0;
}

参考博客

更多代码见github