手写堆与堆的常见操作

什么是堆

堆是一种特殊的树形数据结构，它满足以下两个条件：
堆是一个完全二叉树：即除了最后一层外，每一层都是满的，且最后一层上的节点都集中在左侧。
堆中每个节点的值都要大于等于（或小于等于）其子节点的值：如果每个节点的值都大于等于其子节点的值，我们称之为“大根堆”；如果每个节点的值都小于等于其子节点的值，则称之为“小根堆”。
堆通常用来实现优先队列，通过维护堆顶元素的位置和值，可以快速取出当前队列中的最小（或最大）值，并且支持插入、删除、修改操作。堆排序算法就是利用堆这种数据结构来实现的。
堆可以使用数组来存储，通过下标计算父节点、左右子节点的位置，具有空间效率高、插入、删除元素的时间复杂度为O(log n)等优点，在算法设计中得到广泛应用。

如何建堆(以小根堆为例)

在这里先说下堆的两个操作 down(int x) 和up(int x) 操作.

void down(int x)
{

    int temp = x; //左右孩子中最小值
    if(  2*x <= t &&   h[2*x] < h[temp]) temp =2*x;
    if(2*x + 1 <= t && h[2*x + 1] < h[temp]) temp = 2*x + 1;
    if(temp !=x) {

        swap(h[x],h[temp]);
        down(temp); //递归下去直到没有孩子或本身为最小值结束
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13

1

down和up的说明

• down()使得大的元素节点向下沉.
• up()使得小的元素向上浮.------------像极了在水里.堆中最小值为h(1).

用一维数组的方式来存储,下标从1开始,因为来是一个完全二叉树,从上到下在从左到右遍历,结点的编号是从1-n.每个结点若存在左孩子节点,则左孩子节点的编号为2*i,同理,右孩子节点的编号为2*i+1.一个节点的父节点的编号为i/2(i/2已经是向下取整).那么,新建小根堆时,孩子节点总大于等于其根节点.堆(看成完全二叉树)的最后一层元素最多为 n/2.从下向上看,第二层元素最多为 n/4n,第三层为n/8,第n层为n/2^n.
于是建堆完全可以使用down()操作完成,从n/2个节点开始,down()的操作规模:
n/21+n/42+n/83+……+n/2^n(n-1)(等差数列/等比数列求和)->错位相减 ->结果<(小于) n .所以建堆的时间复杂度近视于O(N).

代码实现(可以用down建堆,也可以用up建堆)

   for(int i = n/2; i;i--) down(i); //完全二叉树的性质,小于等于n/2的节点为分支节点. 大于n/2的为叶子节点
1

或者是(up建堆)

void up(int x)
{
   
   while(x/2 &&  h[x] < h[x/2])
   {
       swap(h[x],h[x/2]);
       x/=2;
       
   }
}
1
2
3
4
5
6
7
8
9
10

堆的相关操作

1. 插入一个数 heap[ ++ size] = x; up(size);
2. 求集合中的最小值 heap[1]
3. 删除最小值 heap[1] = heap[size]; size – ;down(1);
4. 删除任意一个元素 heap[k] = heap[size]; size – ;up(k); down(k);
5. 修改任意一个元素 heap[k] = x; up(k); down(k);

修改和删除任意一个元素up和down操作只会执行一次.两个都写,但up()和down()内做了判断.

堆排序

#include "iostream"

#include "algorithm"
using namespace std;
const int N = 1E5+10;
int h[N];
int n,m,t;
void down(int x)
{

    int temp = x; //左右孩子中最小值
    if(  2*x <= t &&   h[2*x] < h[temp]) temp =2*x;
    if(2*x + 1 <= t && h[2*x + 1] < h[temp]) temp = 2*x + 1;
    if(temp !=x) {

        swap(h[x],h[temp]);
        down(temp); //递归下去直到没有孩子或本身为最小值结束
    }

}
int main()
{
    cin>>n>>m;
    t = n;
    for(int i = 1 ; i <= n ;i++)
    {
        cin>>h[i];
    }

    for(int i = n/2; i;i--) down(i);

    while(m--)
    {
         printf("%d ",h[1]);
         h[1] = h[t--];
        down(1);
    }



    return 0;
}


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

堆的相关操作(代码实现)

1. 插入一个数 heap[ ++ size] = x; up(size);
2. 求集合中的最小值 heap[1]
3. 删除最小值 heap[1] = heap[size]; size – ;down(1);
4. 删除任意一个元素 heap[k] = heap[size]; size – ;up(k); down(k);
5. 修改任意一个元素 heap[k] = x; up(k); down(k);

案例代码

#include "iostream"

#include "algorithm"
using namespace std;
const int N = 1E5 + 10;
int h[N];
int n, m, t; //t为size大小




void up(int x)
{
    while (x / 2 && h[x] < h[x / 2])
    {
        swap(h[x], h[x / 2]);
        x /= 2;

    }
}


void down(int x)
{

    int temp = x; //左右孩子中最小值
    if (2 * x <= t && h[2 * x] < h[temp]) temp = 2 * x;
    if (2 * x + 1 <= t && h[2 * x + 1] < h[temp]) temp = 2 * x + 1;
    if (temp != x) {

        swap(h[x], h[temp]);
        down(temp); //递归下去直到没有孩子或本身为最小值结束
    }

}

//求堆里的最小值
void getmin()
{
    int ret = h[1];
 
    cout << "最小值为" << ret << endl;
     
}

// 插入一个数
void insert(int x)
{

    h[++t] = x;
    up(t);
    cout << "插入成功" << endl;

}
//删除最小值
void delMin()
{
    h[1] = h[t];
    t--;
    down(1);
    cout << "删除成功" << endl;
}
//删除任意一个元素 下标为k
void delKnum(int k)
{
    h[k] = h[t];
    t--;
    down(k);
    up(k);
}

//修改任意一个元素  修改下标为k的数的值为x
void modifyKnum(int k, int x)
{
    h[k] = x;
    up(k);
    down(k);

}


void menu()
{
    cout << "1:求堆里的最小值\r\n";
    cout << "2:插入一个数\r\n";
    cout << "3:删除最小值\r\n";
    cout << "4:删除任意一个元素\r\n";
    cout << "5:修改任意一个元素\r\n";
}
int main()
{
    cin >> n >> m;
    t = n;
    for (int i = 1; i <= n; i++)
    {
        h[i] = i;

    }

    for (int i = n / 2; i; i--) down(i);

   
    int op = 0;
    do {
        menu();
        cout << "输入操作数" << endl;
        cin >> op;
        switch (op)
        {

        case 1:
            getmin();
            break;
        case 2: {
            int x = 0;
            cin >> x;
            insert(x);
        }
            break;
        case 3:
            delMin();
            break;
        case 4:
        {


            int k = 0;
            cin >> k;
            delKnum(k);

        }
            break;
        case 5:
        {

            int k, x;
            cin >> k >> x;
            modifyKnum(k, x);

        }
            break;
        default:
            break;
        }

    } while (op != 0);
     


    return 0;
}
 
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