数据结构-01-堆和二叉堆

字数统计: 3.2k字   |   阅读时长≈ 14分钟

数据结构-01-堆和二叉堆

参考博客 ： https://www.cnblogs.com/skywang12345/p/3603935.html

本章介绍二叉堆，二叉堆就是通常我们所说的数据结构中”堆”中的一种。

1. 堆的定义

  • 堆（heap） ，这里所说的堆是数据结构中的堆，而不是内存模型中的堆。

  • 堆通常可以被看做一棵树，它满足以下性质

    • 堆中任意节点的值总是不大于（不小于）其子节点的值
    • 堆总是一个完全树

  • 将任意节点不大于其子节点的堆叫做最小堆或小根堆

  • 将任意节点不小于其子节点的堆叫做最大堆或大根堆

常见的堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等等。

2. 二叉堆的定义

二叉堆是完全二元树或者是近似完全二元树，它分为两种：最大堆和最小堆。

  • 最大堆：父节点的键值总是大于或者等于任何一个子节点的键值。
  • 最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

示意图如下：

mark

二叉堆一般都是通过数组来实现。数组实现的二叉堆，父节点和子节点的位置存在一定的关系。

  • 有时候，我们将”二叉堆的第一个元素”放在数组索引 0 的位置，有时候放在1的位置。当然，他们的本质一样（都是二叉堆），只是实现上稍微有一丁点区别
  • 假设”第一个元素”在数组中的索引为 0 的话，则父节点和子节点的位置关系如下：
    • 索引为i的左孩子的索引是 （2i+1);
    • 索引为i的左孩子的索引是 (2i+2);
    • 索引为i的父节点索引是floor((i-1)/2);

mark

  • 假设”第一个元素”在数组中的索引为 1 的话，则父节点和子节点的位置关系如下：
    • 索引为i的左孩子的索引是 (2i);
    • 索引为i的左孩子的索引是 (2i+1);
    • 索引为i的父结点的索引是floor(i/2);

mark

注意：本文二叉堆的实现统统都是采用”二叉堆第一个元素在数组索引为0”的方式！

3. 二叉堆的图文解析

在前面，我们已经了解到：”最大堆”和”最小堆”是对称关系。这也意味着，了解其中之一即可。本节的图文解析是以”最大堆”来进行介绍的。

二叉堆的核心是“添加节点”和“删除节点”，理解这两个算法，二叉堆也就基本掌握了。下面对它们进行介绍。

3.1 添加

假设在最大堆[90,80,70,60,40,30,20,10,50]种添加85，需要执行的步骤如下：

mark

如上图所示，当向最大堆中添加数据时候；先将数据加入到最大堆的最后，然后尽可能把这个元素向上挪，直到挪不动位置。

将85添加到[90,80,70,60,40,30,20,10,50]中后，最大堆变成了[90,85,70,60,80,30,20,10,50,40]。

最大堆的插入代码(Java语言)

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
/*
 * 最大堆的向上调整算法(从start开始向上直到0，调整堆)
 *
 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 参数说明：
 *     start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
 */
protected void filterup(int start) {
    int c = start;            // 当前节点(current)的位置
    int p = (c-1)/2;          // 父(parent)结点的位置 
    T tmp = mHeap.get(c);     // 当前节点(current)的大小

    while(c > 0) {
        int cmp = mHeap.get(p).compareTo(tmp);
        if(cmp >= 0)
            break;
        else {
            mHeap.set(c, mHeap.get(p));
            c = p;
            p = (p-1)/2;   
        }       
    }
    // 最后再把值换上去
    mHeap.set(c, tmp);
}
  
/* 
 * 将data插入到二叉堆中
 */
public void insert(T data) {
    int size = mHeap.size();

    mHeap.add(data);     // 将"数组"插在表尾
    filterup(size);        // 向上调整堆
}

3.2 删除

假设从最大堆[90,85,70,60,80,30,20,10,50,40]中删除90，需要执行的步骤如下：

mark

从[90,85,70,60,80,30,20,10,50,40]删除90之后，最大堆变成了[85,80,70,60,40,30,20,10,50]。

如上图所示，当从最大堆中删除数据时候；

  • 先删除该数据，然后用最大堆中的最后一个元素插入这个空位。
  • 接着，把这个空位尽量向下挪，直到剩余数据变成一个最大堆。

注意：考虑从最大堆[90,85,70,60,80,30,20,10,50,40]中删除60，执行的步骤不能单纯的用它的子节点来替换；而必须考虑到”替换后的树仍然要是最大堆”！

mark

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
/* 
 * 最大堆的向下调整算法
 *
 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 参数说明：
 *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
 *     end   -- 截至范围(一般为数组中最后一个元素的索引)
 */
protected void filterdown(int start, int end) {
    int c = start;          // 当前(current)节点的位置
    int l = 2*c + 1;     // 左(left)孩子的位置
    T tmp = mHeap.get(c);    // 当前(current)节点的大小

    while(l <= end) {
        int cmp = mHeap.get(l).compareTo(mHeap.get(l+1));
        // "l"是左孩子，"l+1"是右孩子
        if(l < end && cmp<0)
            l++;        // 左右两孩子中选择较大者，即mHeap[l+1]
        cmp = tmp.compareTo(mHeap.get(l));
        if(cmp >= 0)
            break;        //调整结束
        else {
            mHeap.set(c, mHeap.get(l));
            c = l;
            l = 2*l + 1;   
        }       
    }   
    mHeap.set(c, tmp);
}

/*
 * 删除最大堆中的data
 *
 * 返回值：
 *      0，成功
 *     -1，失败
 */
public int remove(T data) {
    // 如果"堆"已空，则返回-1
    if(mHeap.isEmpty() == true)
        return -1;

    // 获取data在数组中的索引
    int index = mHeap.indexOf(data);
    if (index==-1)
        return -1;

    int size = mHeap.size();
    mHeap.set(index, mHeap.get(size - 1));   // 用最后元素填补
    mHeap.remove(size - 1);                // 删除最后的元素

    if (mHeap.size() > 1)
        filterdown(index, mHeap.size()-1);    // 从index号位置开始自上向下调整为最大堆

    return 0;
}

4. 完整源码

  • 最大堆的实现（MaxHeap.java）
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
package Heap;

// 二叉堆(最大堆) 实现

import java.util.ArrayList;
import java.util.List;

public class MaxHeap <T extends Comparable<T>>{

    private List<T> mHeap;    // 队列(实际上是动态数组ArrayList的实例)


    public MaxHeap(){
        this.mHeap = new ArrayList<T>();
    }


    /*
     * 最大堆的向下调整算法
     *
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * 参数说明：
     *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
     *     end   -- 截至范围(一般为数组中最后一个元素的索引)
     */

    protected void filterdown(int start,int end){
        int c = start;       // 当前节点的位置
        int l = 2*c + 1;     // 左孩子的位置
        T tmp = mHeap.get(c);// 当前节点的大小

        while (l <= end){
            int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1));
            // "l"是左孩子，"l+1"是右孩子

            if (l < end && cmp < 0){
                l ++;   // 左右两孩子中选择较大者，即mHeap[l+1]
            }

            cmp = tmp.compareTo(mHeap.get(l));
            if (cmp >= 0){
                break;
            }else {
                mHeap.set(c,mHeap.get(l));  // 用数组最后一个元素放到该位置
                c = l;              // 索引变为其父节点
                l = 2*l + 1;        // 父节点变为原子节点
            }
        }

        mHeap.set(c,tmp);
    }


    /*
    * 删除最大堆中的data
    *
    * 返回值：
    *      0，成功
    *     -1，失败
    */

    public int remove(T data){
    // 如果"堆"已空，则返回-1
        if(mHeap.isEmpty() == true){
            return -1;
        }

        // 获取data在数组中的索引
        int index = mHeap.indexOf(data);
        if (index==-1){
            return -1;
        }

        int size = mHeap.size();
        mHeap.set(index, mHeap.get(size-1));    // 用最后元素填补
        mHeap.remove(size - 1);           // 删除最后的元素

        if (mHeap.size() > 1) {
            filterdown(index, mHeap.size()-1);    // 从index号位置开始自上向下调整为最小堆
        }
        return 0;
    }


    /*
 * 最大堆的向上调整算法(从start开始向上直到0，调整堆)
 *
 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 参数说明：
 *     start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
 */

    protected void filterup(int start){
        int c = start;          // 当前节点的位置
        int p = (c - 1)/2;      // 父节点的位置
        T tmp = mHeap.get(c);   // 当前索引对应的值


        while (c > 0){
            int cmp = mHeap.get(p).compareTo(tmp);
            if (cmp >= 0){
                break;
            }else {
                mHeap.set(c,mHeap.get(p));
                c = p;
                p = (p - 1)/2;
            }
        }

        mHeap.set(c,tmp);
    }

    /**
     * 将data插入到二叉堆中
     */
    public void insert(T data){
        int size = mHeap.size();

        mHeap.add(data);  // 首先将元素插到数组末尾
        filterup(size);    // 向上调整堆
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < mHeap.size(); i++) {
            sb.append(mHeap.get(i) + " ");
        }
        return sb.toString();
    }

    // 测试用例
    public static void main(String[] args) {
        int i;
        int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
        MaxHeap<Integer> tree = new MaxHeap<Integer>();

        System.out.printf("== 依次添加: ");
        for(i = 0; i < a.length; i++) {
            System.out.printf("%d ", a[i]);
            tree.insert(a[i]);
        }

        System.out.printf("\n== 最 大 堆: %s", tree);

        i=85;
        tree.insert(i);
        System.out.printf("\n== 添加元素: %d", i);
        System.out.printf("\n== 最 大 堆: %s", tree);

        i=90;
        tree.remove(i);
        System.out.printf("\n== 删除元素: %d", i);
        System.out.printf("\n== 最 大 堆: %s", tree);
        System.out.printf("\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
package Heap;

// 二叉堆(最小堆)

import java.util.ArrayList;
import java.util.List;

public class MinHeap<T extends Comparable<T>> {

    private List<T> mHeap;        // 存放堆的数组

    public MinHeap() {
        this.mHeap = new ArrayList<T>();
    }

    /*
     * 最小堆的向下调整算法
     *
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * 参数说明：
     *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
     *     end   -- 截至范围(一般为数组中最后一个元素的索引)
     */
    protected void filterdown(int start, int end) {
        int c = start;          // 当前(current)节点的位置
        int l = 2*c + 1;     	// 左(left)孩子的位置
        T tmp = mHeap.get(c);    // 当前(current)节点的大小

        while(l <= end) {
            int cmp = mHeap.get(l).compareTo(mHeap.get(l+1));
            // "l"是左孩子，"l+1"是右孩子
            if(l < end && cmp>0)
                l++;        // 左右两孩子中选择较小者，即mHeap[l+1]

            cmp = tmp.compareTo(mHeap.get(l));
            if(cmp <= 0)
                break;        //调整结束
            else {
                mHeap.set(c, mHeap.get(l));
                c = l;
                l = 2*l + 1;
            }
        }
        mHeap.set(c, tmp);
    }

    /*
     * 最小堆的删除
     *
     * 返回值：
     *     成功，返回被删除的值
     *     失败，返回null
     */
    public int remove(T data) {
        // 如果"堆"已空，则返回-1
        if(mHeap.isEmpty() == true)
            return -1;

        // 获取data在数组中的索引
        int index = mHeap.indexOf(data);
        if (index==-1)
            return -1;

        int size = mHeap.size();
        mHeap.set(index, mHeap.get(size-1));   // 用最后元素填补
        mHeap.remove(size - 1);                // 删除最后的元素

        if (mHeap.size() > 1)
            filterdown(index, mHeap.size() - 1);    // 从index号位置开始自上向下调整为最小堆

        return 0;
    }

    /*
     * 最小堆的向上调整算法(从start开始向上直到0，调整堆)
     *
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * 参数说明：
     *     start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
     */
    protected void filterup(int start) {
        int c = start;            // 当前节点(current)的位置
        int p = (c-1)/2;          // 父(parent)结点的位置
        T tmp = mHeap.get(c);     // 当前节点(current)的大小

        while(c > 0) {
            int cmp = mHeap.get(p).compareTo(tmp);
            if(cmp <= 0)
                break;
            else {
                mHeap.set(c, mHeap.get(p));
                c = p;
                p = (p-1)/2;
            }
        }
        // 最后再把值换上去
        mHeap.set(c, tmp);
    }

    /*
     * 将data插入到二叉堆中
     */
    public void insert(T data) {
        int size = mHeap.size();

        mHeap.add(data);       // 将"数组"插在表尾
        filterup(size);        // 向上调整堆
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<mHeap.size(); i++)
            sb.append(mHeap.get(i) +" ");

        return sb.toString();
    }

    public static void main(String[] args) {
        int i;
        int a[] = {80, 40, 30, 60, 90, 70, 10, 50, 20};
        MinHeap<Integer> tree=new MinHeap<Integer>();

        System.out.printf("== 依次添加: ");
        for(i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
            tree.insert(a[i]);
        }

        System.out.printf("\n== 最 小 堆: %s", tree);

        i=15;
        tree.insert(i);
        System.out.printf("\n== 添加元素: %d", i);
        System.out.printf("\n== 最 小 堆: %s", tree);

        i=10;
        tree.remove(i);
        System.out.printf("\n== 删除元素: %d", i);
        System.out.printf("\n== 最 小 堆: %s", tree);
        System.out.printf("\n");
    }
}

运行结果：

  • 最大堆(MaxHeap.java)的运行结果：
1
2
3
4
5
6
== 依次添加: 10 40 30 60 90 70 20 50 80 
== 最 大 堆: 90 80 70 60 40 30 20 10 50 
== 添加元素: 85
== 最 大 堆: 90 85 70 60 80 30 20 10 50 40 
== 删除元素: 90
== 最 大 堆: 85 80 70 60 40 30 20 10 50
  • 最小堆(MinHeap.java)的运行结果：
1
2
3
4
5
== 最 小 堆: 10 20 30 50 90 70 40 80 60 
== 添加元素: 15
== 最 小 堆: 10 15 30 50 20 70 40 80 60 90 
== 删除元素: 10
== 最 小 堆: 15 20 30 50 90 70 40 80 60
打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2019-2022 Zhuuu
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信