算法基础：堆【以大根堆为例】

二叉堆

二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆

◼️ 鉴于完全二叉树的一些特性，二叉堆的底层(物理结构)一般用数组实现即可

◼️ 索引 i 的规律( n 是元素数量)

如果 i = 0 ，它是根节点

如果 i > 0 ，它的父节点的索引为 floor( (i – 1) / 2 ) （向下取整）

如果 2i + 1 ≤ n – 1，它的左子节点的索引为 2i + 1

如果 2i + 1 > n – 1 ，它无左子节点

如果 2i + 2 ≤ n – 1 ，它的右子节点的索引为 2i + 2

如果 2i + 2 > n – 1 ，它无右子节点

大根堆的例子

public class HeapSort {

    public static void main(String[] args) {
        System.out.println("大顶堆测试");
        int[] arr = {68, 72, 43, 50, 38, 10, 90, 65};

        MyHeapSort obj = new MyHeapSort();
        for (int i : arr) {
            obj.add(i);
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = obj.remove();
        }

        System.out.println("堆排序后：");
        for (int i : arr) {
            System.out.print(i + "  ");
        }
        // 90  72  68  65  50  43  38  10
        System.out.println();
        for (int i : arr) {  //堆空了，重新添加元素进去
            obj.add(i);
        }
        System.out.println("获取堆顶元素：" + obj.get());


        System.out.println("替换堆顶元素为13：" + obj.replace(13));
        System.out.println("替换堆顶元素为13后的堆顶元素：" + obj.get());
    }


    static class MyHeapSort {  //大根heap  由大到小的排序
        public int[] arr;
        public int size;
        public int defaultSize = 10;

        public MyHeapSort() {
            size = 0;
            arr = new int[defaultSize];
        }

        //扩容代码
        public void ensureCap(int cap) {
            int oldcap = arr.length;
            if (oldcap >= cap) return;
            //新容量为旧容量的1.5倍
            int newcap = oldcap + oldcap >> 1;
            int[] newarr = new int[newcap];
            for (int i = 0; i < size; i++) {
                newarr[i] = arr[i];
            }
            arr = newarr;
        }

        public void add(int val) {
            ensureCap(size + 1);
            arr[size++] = val;
            shiftup(size - 1);
        }

        //上滤
        public void shiftup(int index) {
            int cur = arr[index];
            while (index > 0) {
                int pindex = (index - 1) / 2;
                int parent = arr[pindex];
                if (parent >= cur) break;
                arr[index] = parent;
                index = pindex;
            }
            arr[index] = cur;
        }

        //删除：二叉堆的删除是删除堆顶元素
        //思路：最后一个元素代替堆顶元素，删除最后一个元素，然后下窜
        public int remove() {
            int last = --size;
            int root = arr[0];
            arr[0] = arr[last];
            //arr[last] 不用管了，因为长度要减1，减1后，最后一个元素也不存在了
            shiftdown(0);
            return root;
        }

        public void shiftdown(int index) {
            int half = size >> 1;
            int root = arr[0];
            while (index < half) {
                //index:只有左子节点，或者左右子节点都有
                int pos = (index << 1) + 1;
                int child = arr[pos];
                int right = pos + 1;
                if (right < size && arr[right] > arr[pos]) {
                    pos = right;
                    child = arr[right];
                }

                if (root > child) break;
                arr[index] = child;
                index = pos;
            }
            arr[index] = root;
        }


        public int get() {  //获取堆顶元素
            if (size == 0) return Integer.MIN_VALUE;
            return arr[0];
        }

        //删除堆顶的元素的同时，插入一个新元素
        public int replace(int ele) { //替换堆顶元素
            int root = Integer.MIN_VALUE;
            if (size == 0) {
                arr[0] = ele;
                size++;
            } else {
                root = arr[0];
                arr[0] = ele;
                shiftdown(0);
            }

            return root;
        }
    }
}



/*
大顶堆测试
堆排序后：
90  72  68  65  50  43  38  10
获取堆顶元素：90
替换堆顶元素为13：90
替换堆顶元素为13后的堆顶元素：72
 */

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