优先级队列

题目

实现一个优先级队列（二叉堆）

实现代码

通过完全二叉树来实现，并且底层使用数组来构建完全二叉树的逻辑结构


public class PriorityQueueDemo {

  static class PriorityQueue {

    private final int[] arr;

    private int size;

    public PriorityQueue(int capacity) {

      // 从1开始
      arr = new int[capacity + 1];
      size = 0;
    }

    // 左边节点索引
    public int left(int node) {

      return node * 2;
    }

    // 右边节点索引
    public int right(int node) {

      return node * 2 + 1;
    }

    // 父节点索引
    public int parent(int node) {

      return node / 2;
    }

    // 节点下沉
    public void sink(int node) {

      int min = node;
      while (left(node) <= size || right(node) <= size) {

        if (left(node) <= size && arr[left(node)] < arr[min]) {
          min = left(node);
        }
        if (right(node) <= size && arr[right(node)] < arr[min]) {
          min = right(node);
        }
        if (min == node) {
          return;
        }
        int tmp = arr[node];
        arr[node] = arr[min];
        arr[min] = tmp;
        node = min;
      }
    }

    // 节点上升
    public void rise(int node) {

      while (node > 1 && arr[parent(node)] > arr[node]) {
        int tmp = arr[node];
        arr[node] = arr[parent(node)];
        arr[parent(node)] = tmp;
        node = parent(node);
      }
    }

    // 添加
    public void push(int val) {

      arr[size + 1] = val;
      // 上浮
      rise(size + 1);
      size++;
    }

    // 删除
    public int pop() {

      int tmp = arr[1];
      arr[1] = arr[size];
      size--;
      // 下沉
      sink(1);
      return tmp;
    }
  }

  public static void main(String[] args) {

    PriorityQueue queue = new PriorityQueue(5);
    queue.push(3);
    queue.push(2);
    queue.push(1);
    queue.push(5);
    queue.push(4);
    System.out.println(queue.pop()); // 1
    System.out.println(queue.pop()); // 2
    System.out.println(queue.pop()); // 3
    System.out.println(queue.pop()); // 4
    System.out.println(queue.pop()); // 5
  }
}