​

​1. 堆的概念

堆在逻辑上是一棵完全二叉树，物理上是保存在数组中的。满足任意节点的值都大于其子树中节点的值，叫做大根堆，任意节点的值都小于其子树中节点的值叫做小根堆。堆的基本作用是快速找集合中的最值。

2. 最大堆的实现

2.1 向堆中添加元素（进行上浮操作 siftUp）

数组尾插添加元素，添加元素后，可能会破坏最大堆的定义，因此进行元素上浮操作 siftUp，需要调整前，左右子树已经是一个堆，才能调整。然后进行 siftUp 操作直到把当前元素上浮到合适位置。

public void add(int val) {
        // 1. 向数组末尾添加元素
        data.add(val);
        // 2. 调整当前堆的结构，使其仍然满足最大堆的性质
        siftUp(data.size() - 1);
    }
    
    // 元素上浮操作
    private void siftUp(int i) {
        while(i > 0 && data.get(i) > data.get(parent(i))) {
            swap(i,parent(i));
            // 继续向上判断交换后父节点向上的节点关系
            i = parent(i);
        }
    }
    
    private void swap(int i, int parent) {
        int temp = data.get(i);
        int parentval = data.get(parent);
        data.set(i,parentval);
        data.set(parent,temp);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.2 在堆中取出最大值

当前是最大堆，它的最大值就在根节点，但是不能直接取出。先将堆中最后一个元素替换到堆顶，删除最后一个元素，然后进行下沉操作（siftDown）使其仍然满足最大堆的性质。

public int extractMax() {
        if (isEmpty()) {
            System.err.println("heap is empty!");
            return -1;
        }
        int max = data.get(0);
        // 将最后一个元素顶到堆顶
        data.set(0,data.get(0));
        int lastaval = data.get(data.size() - 1);
        data.set(0,lastaval);
        data.remove(data.size() - 1);
        siftDown(0);
        return max;
    }

    private void siftDown(int i) {
        while (leftChild(i) < data.size()) {
            int j = leftChild(i);
            // 取出左右孩子的最大值
            if (right(i) < data.size()) {
                int leftVal = data.get(leftChild(i));
                int rightVal = data.get(right(i));
                if (leftVal < rightVal) {
                    j = j + 1;
                }
            }
            // j 一定是左右孩子最大值的索引
            // data[i] 和 data[j]
            if (data.get(i) >= data.get(j)) {
                // 当前节点已经大于左右孩子，下沉结束
                break;
            } else {
                // swap
                swap(i,j);
                i = j;
            }
        }
    }
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

2.3 建堆（heapify）

将任意数组调整为堆，这个数组逻辑上可以看作是一棵完全二叉树，但还不是一个堆。从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点。

public void MaxHeap(int[] arr) {
    ArrayList res = new ArrayList<>(arr.length);
    //1.先将所有元素复制到data数组中
    for (int i : arr) {
        res.add(i);
        size ++;
    }
    //2.从最后一个非叶子节点开始进行siftDown操作
    for (int i = parent(size - 1); i >= 0; i--) {
        siftDown(i);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

3. 优先级队列

优先级队列按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。优先级队列的实现方式有很多，但最常见的是使用堆来构建。

/**
 * 基于堆实现优先级队列
 */
public class PriorityQueue implements Queue {
    private MaxHeap heap;
    public PriorityQueue() {
        heap = new MaxHeap();
    }
    
    @Override
    public void offer(Integer val) {
        heap.add(val);
    }
    //所谓优先级就是最大值
    @Override
    public Integer poll() {
        return heap.extractMax();
    }

    @Override
    public Integer peek() {
        return heap.peekMax();
    }

    @Override
    public boolean isEmpty() {
        return heap.isEmpty();
    }
}

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

活动地址：CSDN21天学习挑战赛

​