2.7 優(yōu)先級隊列

無序數(shù)組實現(xiàn)

要點

1. 入隊保持順序
2. 出隊前找到優(yōu)先級最高的出隊，相當(dāng)于一次選擇排序

public class PriorityQueue1<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    public PriorityQueue1(int capacity) {
        array = new Priority[capacity];
    }

    @Override // O(1)
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        array[size++] = e;
        return true;
    }

    // 返回優(yōu)先級最高的索引值
    private int selectMax() {
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[max].priority()) {
                max = i;
            }
        }
        return max;
    }

    @Override // O(n)
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax();
        E e = (E) array[max];
        remove(max);
        return e;
    }

    private void remove(int index) {
        if (index < size - 1) {
            System.arraycopy(array, index + 1,
                    array, index, size - 1 - index);
        }
        array[--size] = null; // help GC
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax();
        return (E) array[max];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

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

• 視頻中忘記了 help GC，注意一下

有序數(shù)組實現(xiàn)

要點

1. 入隊后排好序，優(yōu)先級最高的排列在尾部
2. 出隊只需刪除尾部元素即可

public class PriorityQueue2<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    public PriorityQueue2(int capacity) {
        array = new Priority[capacity];
    }

    // O(n)
    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        insert(e);
        size++;
        return true;
    }

    // 一輪插入排序
    private void insert(E e) {
        int i = size - 1;
        while (i >= 0 && array[i].priority() > e.priority()) {
            array[i + 1] = array[i];
            i--;
        }
        array[i + 1] = e;
    }

    // O(1)
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E e = (E) array[size - 1];
        array[--size] = null; // help GC
        return e;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

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

堆實現(xiàn)

計算機(jī)科學(xué)中，堆是一種基于樹的數(shù)據(jù)結(jié)構(gòu)，通常用完全二叉樹實現(xiàn)。堆的特性如下

• 在大頂堆中，任意節(jié)點 C 與它的父節(jié)點 P 符合
• 而小頂堆中，任意節(jié)點 C 與它的父節(jié)點 P 符合
• 最頂層的節(jié)點（沒有父親）稱之為 root 根節(jié)點

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node

例1 - 滿二叉樹（Full Binary Tree）特點：每一層都是填滿的

image.png

例2 - 完全二叉樹（Complete Binary Tree）特點：最后一層可能未填滿，靠左對齊

image.png

例3 - 大頂堆

image.png

例4 - 小頂堆

image.png

完全二叉樹可以使用數(shù)組來表示

image.png

特征

• 如果從索引 0 開始存儲節(jié)點數(shù)據(jù)
  • 節(jié)點 的父節(jié)點為 ，當(dāng) 時
  • 節(jié)點 的左子節(jié)點為 ，右子節(jié)點為 ，當(dāng)然它們得
• 如果從索引 1 開始存儲節(jié)點數(shù)據(jù)
  • 節(jié)點 的父節(jié)點為 ，當(dāng) 時
  • 節(jié)點 的左子節(jié)點為 ，右子節(jié)點為 ，同樣得

代碼

public class PriorityQueue4<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    public PriorityQueue4(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E offered) {
        if (isFull()) {
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while (child > 0 && offered.priority() > array[parent].priority()) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = offered;
        return true;
    }


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

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0, size - 1);
        size--;
        Priority e = array[size];
        array[size] = null;
        
        shiftDown(0);        
        return (E) e;
    }

    void shiftDown(int parent) {
        int left = 2 * parent + 1;
        int right = left + 1;
        int max = parent;
        if (left < size && array[left].priority() > array[max].priority()) {
            max = left;
        }
        if (right < size && array[right].priority() > array[max].priority()) {
            max = right;
        }
        if (max != parent) {
            swap(max, parent);
            shiftDown(max);
        }
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

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