定义以及特征

计算机科学中，堆是一种基于树的数据结构，通常用完全二叉树实现。堆的特性如下：

  • 在大顶堆中，任意节点C与它的父节点P符合 P.value >= C.value
  • 在小顶堆中，任意节点C与它的父节点P符合 P.value <= C.value
  • 而顶层的节点(没有父亲)称之为root根节点

特征：如果把完全二叉树放在数组的话，斜着放，一个元素一个坑

  • 如果从索引0开始存储节点数据

    • 节点i的父节点为floor((i - 1)/2),当i > 0时
    • 节点i的左子节点为2i + 1，右子节点为2i + 2，当然他们得 < size

  • 如果从索引1开始存储节点数据

    • 节点i的父节点为floor(i/2),当i > 0时
    • 节点i的左子节点为2i，右子节点为2i + 1，同样得 < size

Fkoyd 建堆方法

他提出了新的建堆方法，时间复杂度O(n)
1、找到最后一个非叶子节点
2、从后向前，对每个节点执行下潜

下面代码包含了完整的建堆以及大顶堆的方法

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
//建堆，大顶堆
public class MaxHeap {
    int[] array;
    int size;

    public MaxHeap(int capacity) {
        this.array = new int[capacity];
    }

    public MaxHeap(int[] array) {
        this.array = array;
        this.size = array.length;
        heapify();
    }

    //建堆(大顶堆)
    private void heapify() {
        //如何找到最后这个非叶子节点  size/2 - 1
        for (int i = size / 2 - 1; i >= 0; i--) {
            down(i);
        }
    }

    // 将 parent 索引处的元素下潜；与两个孩子较大者交换，直至没孩子或孩子没它大
    private void down(int parent) {
        //找到左右孩子
        int left = parent * 2 + 1;
        int right = left + 1;
        //假设最大值就是父亲
        int max = parent;
        if(left < size && array[left] > array[max]) { //没超出索引且孩子比父亲大最大值更改
            max = left;
        }
        if(right < size && array[right] > array[max]) {
            max = right;
        }
        if(max != parent) {// 找到更大的孩子
            swap(max, parent);
            //通过递归继续下潜
            down(max);
        }
    }

    private void swap(int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    /**
     * 获取堆顶元素(不删除)
     * @return 堆顶元素
     */
    public int peek() {
        return array[0];
    }

    /**
     * 删除堆顶元素并返回
     * @return 堆顶元素
     */
    public int poll(){
        int top = array[0];
        //删除操作
        //1、先把堆顶元素和最后一个元素交换
        swap(0,size - 1);
        size--;
        //2、下潜,重新实现大顶堆
        down(0);
        return top;
    }

    /**
     * 删除指定位置的元素
     * @param index-索引
     * @return 被删除元素
     */
    public int poll(int index) {
        //本质上是一样的和其实索引，不得不说老师一定设计过，这代码复用性太高了,tql
        int res = array[index];
        //交换位置
        swap(index, size - 1);
        size--;
        //下潜
        down(index);
        return res;
    }

    /**
     * 替换堆顶元素
     * @param replaced-新元素
     */
    public void replace(int replaced) {
        array[0] = replaced;
        //防止破坏堆的特性
        //下潜
        down(0);
    }

    /**
     * 在堆的尾部添加元素
     * @param offered-新元素
     * @return 是否添加成功
     */
    public boolean offer(int offered) {
        if(size == array.length) {
            return false;
        }
        up(offered);
        size++;
        return true;
    }

    //将offered 元素上浮： 直至offered 小于父元素或到堆顶
    private void up(int offered) {
        int child = size;
        while(child > 0) {
            int parent = (child - 1) / 2;
            if(offered > array[parent]) {
                array[child] = array[parent];
            }else {
                //不比父亲大那么结束上浮
                break;
            }
            child = parent;
        }
        //循环结束都是代表着上浮结束，该把目标值赋值给child索引
        array[child] = offered;
    }
}

实现堆排序

算法描述：
1、heapify建立大顶堆
2、将堆顶与堆底交换(最大元素被交换到堆底)，缩小并下潜调整堆
3、重复第二步直至堆里剩一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
        int[] array = {2,3,1,7,6,4,5};
        MaxHeap maxHeap = new MaxHeap(array);
        System.out.println(Arrays.toString(maxHeap.array));
        while(maxHeap.size > 1) {
            //头尾交换元素
            maxHeap.swap(0, maxHeap.size - 1);
            maxHeap.size--;
            //调整成符合大顶堆
            maxHeap.down(0);
        }
        System.out.println(Arrays.toString(maxHeap.array));
    }

求数组第k大元素(T215)

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
/**
 * 求数组中第K大的元素
 * 解题思路
 * 1、向小顶堆放入前k个元素
 * 2、剩余元素
 *      - 若 <= 堆顶元素，则略过
 *      - 若 >  堆顶元素，则替换堆顶元素
 * 3、这样小顶堆始终保留的都是到目前为止，前K大的元素
 * 4、循环结束，堆顶元素即为第K大元素
 */
public class E02Leetcode215 {
    public int findKthLargest(int[] nums, int k) {
        //小顶堆
        MinHeap heap = new MinHeap(k);
        for (int i = 0; i < k; i++) {
            heap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if(nums[i] > heap.peek()){
                heap.replace(nums[i]);
            }
        }
        return heap.peek();
    }
}

求数据流第k大元素(T703)

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
class KthLargest {

    private MinHeap heap;

    public KthLargest(int k, int[] nums) {
        heap = new MinHeap(k);
        for(int num : nums) {
            add(num);
        }
    }

    //此方法会被不断调用，模拟数据流中新来的元素
    public int add(int val) {
        if (!heap.isFull()) {
            heap.offer(val);
        } else {
            //小于就忽略掉不用做任何操作
            if (val > heap.peek()) {
                heap.replace(val);
            }
        }
        return heap.peek();
    }

    //小顶堆
    public class MinHeap {
        int[] array;
        int size;

        public MinHeap(int capacity) {
            this.array = new int[capacity];
        }

        public MinHeap(int[] array) {
            this.array = array;
            this.size = array.length;
            heapify();
        }

        public boolean isFull() {
            return size == array.length;
        }

        //建堆(大顶堆)
        private void heapify() {
            //如何找到最后这个非叶子节点  size/2 - 1
            for (int i = size / 2 - 1; i >= 0; i--) {
                down(i);
            }
        }

        // 将 parent 索引处的元素下潜；与两个孩子较大者交换，直至没孩子或孩子没它大
        private void down(int parent) {
            //找到左右孩子
            int left = parent * 2 + 1;
            int right = left + 1;
            //假设最大值就是父亲
            int min = parent;
            if(left < size && array[left] < array[min]) { //没超出索引且孩子比父亲大最大值更改
                min = left;
            }
            if(right < size && array[right] < array[min]) {
                min = right;
            }
            if(min != parent) {// 找到更大的孩子
                swap(min, parent);
                //通过递归继续下潜
                down(min);
            }
        }

        private void swap(int i, int j) {
            int t = array[i];
            array[i] = array[j];
            array[j] = t;
        }

        /**
         * 获取堆顶元素(不删除)
         * @return 堆顶元素
         */
        public int peek() {
            return array[0];
        }

        /**
         * 删除堆顶元素并返回
         * @return 堆顶元素
         */
        public int poll(){
            int top = array[0];
            //删除操作
            //1、先把堆顶元素和最后一个元素交换
            swap(0,size - 1);
            size--;
            //2、下潜,重新实现大顶堆
            down(0);
            return top;
        }

        /**
         * 删除指定位置的元素
         * @param index-索引
         * @return 被删除元素
         */
        public int poll(int index) {
            //本质上是一样的和其实索引，不得不说老师一定设计过，这代码复用性太高了,tql
            int res = array[index];
            //交换位置
            swap(index, size - 1);
            size--;
            //下潜
            down(index);
            return res;
        }

        /**
         * 替换堆顶元素
         * @param replaced-新元素
         */
        public void replace(int replaced) {
            array[0] = replaced;
            //防止破坏堆的特性
            //下潜
            down(0);
        }

        /**
         * 在堆的尾部添加元素
         * @param offered-新元素
         * @return 是否添加成功
         */
        public boolean offer(int offered) {
            if(size == array.length) {
                return false;
            }
            up(offered);
            size++;
            return true;
        }

        //将offered 元素上浮： 直至offered 小于父元素或到堆顶
        private void up(int offered) {
            int child = size;
            while(child > 0) {
                int parent = (child - 1) / 2;
                if(offered < array[parent]) {
                    array[child] = array[parent];
                }else {
                    //不比父亲大那么结束上浮
                    break;
                }
                child = parent;
            }
            //循环结束都是代表着上浮结束，该把目标值赋值给child索引
            array[child] = offered;
        }
    }

}

求数据流中位数(T295)

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
class MedianFinder {

    //大顶堆需要加选择构造器
    private PriorityQueue<Integer> left = new PriorityQueue<>(
        (a, b) -> Integer.compare(b, a)
    );

    //java类里默认的优先级队列实现的是小顶堆
    private PriorityQueue<Integer> right = new PriorityQueue<>();

    public MedianFinder() {

    }
    

    /*
        为了保证两边数据量的平衡
            两边个数一样时，左边个数加一
            两边个数不一样时，右边个数加一
        但是随便一个数能直接加入吗？
            左边个数加一时，把新元素加载右边，弹出右边最小的加入左边
            右边个数加一时，把新元素加在左边，弹出左边最小的加入右边
    */
    public void addNum(int num) {
        if(left.size() == right.size()) {
            //左边个数加一时，把新元素加载右边，弹出右边最小的加入左边
            right.offer(num);
            left.offer(right.poll());
        } else {
            //右边个数加一时，把新元素加在左边，弹出左边最小的加入右边
            left.offer(num);
            right.offer(left.poll());
        }
    }
    
    /*
        两边数据一致，左右各取堆顶元素求平均
        左边多一个，取左边堆顶元素
    */
    public double findMedian() {
        if(left.size() == right.size()) {
            return (left.peek() + right.peek()) / 2.0;
        } else {
            return left.peek();
        }
    }
}