Java 数据结构之堆(优先队列)的实现

什么是堆(优先队列)

堆(Heap)是一种数据结构，使用数组实现。堆分为小根堆和大根堆，大根堆满足父节点值大于子节点，小根堆则相反。堆通常被用来实现优先队列(Priority Queue)。

优先队列(Priority Queue)是一个能够让用户迅速查找到队列中最小值（或最大值）的抽象数据类型（ADT）。优先队列通常用堆来实现。

在Java中，堆的实现主要有两种方式：一种是使用Collections的PriorityQueue，一种是手动实现堆。

java.util.PriorityQueue实现

Java中自带的PriorityQueue是一种实现了优先队列的数据结构，底层是一个小根堆。它的具体实现是数组，也可以用数组表达式来看待这个堆 。Java中的PriorityQueue提供了数据结构基本操作的方法：插入、删除、获取队首元素、堆大小等。

下面是Java实现PriorityQueue的示例代码：

import java.util.PriorityQueue;
public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(3);
        pq.add(1);
        pq.add(2);
        System.out.println(pq);
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
    }
}

输出结果：

[1, 3, 2]
1
2
3

上面的示例代码首先创建了一个PriorityQueue对象pq，然后通过add()方法插入元素。最后三个poll()方法依次弹出元素。这里需要注意的是，PriorityQueue是小根堆，poll()方法会弹出堆中的最小元素。

手动实现堆

手动实现堆的方式在工程实践中不常用，但是可以增加对堆的深刻理解。

下面是手动实现堆的示例代码：

public class Heap {
    private int[] heap;
    private int size;
    private int maxSize;

    public Heap(int maxSize) {
        this.maxSize = maxSize;
        this.size = 0;
        this.heap = new int[this.maxSize + 1];
        this.heap[0] = Integer.MIN_VALUE;
    }

    private int parent(int i) {
        return i / 2;
    }

    private int leftChild(int i) {
        return i * 2;
    }

    private int rightChild(int i) {
        return (i * 2) + 1;
    }

    private boolean isLeaf(int i) {
        if (i > size / 2 && i <= size) {
            return true;
        }
        return false;
    }

    private void swap(int i, int j) {
        int temp = this.heap[i];
        this.heap[i] = this.heap[j];
        this.heap[j] = temp;
    }

    public void insert(int element) {
        if (size >= maxSize) {
            return;
        }
        this.heap[++size] = element;
        int current = size;
        while (this.heap[current] < this.heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    public int remove() {
        int popped = this.heap[1];
        this.heap[1] = this.heap[size--];
        heapify(1);
        return popped;
    }

    public void heapify(int i) {
        if (!isLeaf(i)) {
            if (this.heap[i] > this.heap[leftChild(i)] || this.heap[i] > this.heap[rightChild(i)]) {
                if (this.heap[leftChild(i)] < this.heap[rightChild(i)]) {
                    swap(i, leftChild(i));
                    heapify(leftChild(i));
                } else {
                    swap(i, rightChild(i));
                    heapify(rightChild(i));
                }
            }
        }
    }

    public void print() {
        for (int i = 1; i <= size / 2; i++) {
            System.out.print(" PARENT : " + heap[i] + " LEFT CHILD : " + heap[2 * i]
                    + " RIGHT CHILD :" + heap[2 * i + 1]);
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Heap Heap = new Heap(15);
        Heap.insert(5);
        Heap.insert(3);
        Heap.insert(17);
        Heap.insert(10);
        Heap.insert(84);
        Heap.insert(19);
        Heap.insert(6);
        Heap.insert(22);
        Heap.insert(9);

        Heap.print();

        System.out.println("The Min val is " + Heap.remove());
    }
}

输出结果：

 PARENT : 3 LEFT CHILD : 5 RIGHT CHILD :17
 PARENT : 5 LEFT CHILD : 10 RIGHT CHILD :84
 PARENT : 17 LEFT CHILD : 6 RIGHT CHILD :19
 PARENT : 10 LEFT CHILD : 22 RIGHT CHILD :9
The Min val is 3

上面的代码实现了手动创建堆和一些基本操作的方法，例如：insert()、remove()、heapify()以及print()操作。我们可以看到，输出的结果是小根堆的形式，remove()方法会返回堆中的最小元素。