二叉堆和优先队列

设计一个数据结构, 存放整数, 提供以下三个接口

• 获取元素
• 获取最大值
• 删除最大值

可以使用的结构, 动态数组, 双向链表, 平衡二叉搜索树

时间复杂度如下:

可以使用的数据结构

堆

堆, 也是一种树状的数据结构, 常见的堆实现

• 二叉堆, 完全二叉堆
• 多叉堆
• 索引堆
• 二项堆
• 斐波那契堆
• 左倾堆
• 斜堆

堆的性质, 任意节点的值总是大于等于或小于等于子节点的值

如果任意节点的值总是大于等于子节点的值, 称为, 最大堆, 大根堆, 大顶堆

反之, 称为, 最小堆, 小根堆, 小顶堆

堆中的元素必须具备可比性

最大最小堆

堆的接口设计

public interface Heap<E> {
    int size(); // 元素数量
    boolean isEmpty(); // 是否为空
    void clear(); // 清空
    void add(E element); // 添加元素
    E get(); // 获取堆顶元素
    E remove(); // 删除堆顶元素
    E replace(E element); // 删除堆顶元素, 插入一个新元素
}

二叉堆

二叉堆的逻辑结构就是一颗完全二叉树, 所以也叫完全二叉堆

所以二叉堆的底层一般使用数组来实现

索引i 的规律

如果i = 0, 它是根节点

如果i > 0, 它的父节点的索引为(i - 1)/2

如果2i + 1 <= n - 1, 它的左子节点索引为2i + 1

如果2i + 1 > n - 1, 无左子节点

如果2i + 2 <= n - 1, 右子节点索引为2i + 2

如果2i + 2 > n - 1, 无右子节点

完全二叉堆 底层使用数组

添加元素

1. 如果node > 父节点, 与父节点交换位置
2. node <= 父节点, 或者没有父节点, 退出循环

重复以上操作, 这个过程为上滤(SiftUp), 时间复杂度为O(logn)

最大堆添加

在找索引时, 先记录索引值, 最后确定交换位置后, 最终交换位置

最大堆添加优化

删除

最大堆删除

1. 用最后一个节点覆盖根节点
2. 删除最后一个节点
3. 循环执行以下操作
   1. 如果node < 最大子节点, 与最大子节点交换位置
4. 如果node >= 最大子节点, 或者node 没有子节点, 退出循环

这个过程称为下滤(SiftDown), 复杂度为O(logn)

批量建堆

自上而下的上滤

自上而下的上滤

自下而上的下滤

自下而上的下滤

效率对比

效率对比

所有节点的深度之和

叶子节点, 有近n/2 个, 每个叶子节点的深度都是O(logn)

因此, 叶子结点复杂度为O(nlogn)

公式推导

公式推导1 公式推导2

完整代码实现

@SuppressWarnings({"unchecked"})
public abstract class AbstractHeap<E> implements Heap<E> {
    protected int size;
    protected Comparator<E> comparator;
    
    public AbstractHeap(Comparator<E> comparator) {
        this.comparator = comparator;
    }
    
    public AbstractHeap() {
        this(null);
    }
    
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    
    protected int compare(E e1, E e2) {
        return comparator != null ? comparator.compare(e1, e2) : ((Comparable<E>)e1).compareTo(e2);
    }
    
}

/**
 * 最大堆
 * @author null
 *
 * @param <E>
 */
@SuppressWarnings({"unchecked"})
public class BinaryHeap<E> extends AbstractHeap<E> {
    
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;
    
    
    public BinaryHeap(E[] elements, Comparator<E> comparator) {
        super(comparator);
        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            size = elements.length;
            int capacity = Math.max(DEFAULT_CAPACITY, elements.length);
            this.elements = (E[]) new Object[capacity];
            this.size = elements.length;
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            heapify();
        }
    }
    
    public BinaryHeap(E[] elements) {
        this(elements, null);
    }
    
    public BinaryHeap(Comparator<E> comparator) {
        super(comparator);
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
    
    public BinaryHeap() {
        this(null, null);
    }

    @Override
    public void clear() {
        for (int i = 0; i < elements.length; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);
        elements[size++] = element;
        siftUp(size - 1);
    }

    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    @Override
    public E remove() {
        emptyCheck();
        
        E root = elements[0];
        int lastIndex = --size;
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;
        siftDown(0);
        return root;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        
        E root = null;
        if (size == 0) {
            elements[0] = element;
            size++;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }
    
    private void heapify() {
        // 自上而下的上滤
//      for (int i = 1; i < size; i++) {
//          siftUp(i);
//      }
        
        // 自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }
    
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        // 第一个叶子结点的索引,为非叶子节点的数量
        // index < 第一个叶子节点的索引
        // 必须保证index 为非叶子节点
        while (index < half) {
            // index 的节点有两种清空
            // 1. 只有左
            // 2. 同时存在左右
            // 默认为左子节点进行比较
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];
            
            int rightIndex = childIndex + 1;
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
                child = elements[childIndex = rightIndex];
            }
            
            if (compare(element, child) >= 0) break;
            elements[index] = child;
            index = childIndex;
            
        }
        elements[index] = element;
        
    }
    
    private void siftUp(int index) {
//      E e = elements[index];
//      while (index > 0) {
//          int pindex = (index- 1 ) >> 1;
//          E p = elements[pindex];
//          if (compare(e, p) <= 0) return;
//          E tmp = elements[index];
//          elements[index] = elements[pindex];
//          elements[pindex] = tmp;
//          index = pindex;
//      }
        
        E e = elements[index];
        while (index > 0) {
            int pindex = (index -1) >> 1;
            E p = elements[pindex];
            if (compare(e, p) <= 0) break;
            
            elements[index] = p;
            index = pindex;
        }
        elements[index] = e;
    }
    
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) {
            return;
        }
        
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }
    
    private void emptyCheck() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }
    
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
}

Top K 问题

n 个整数中, 找出最大的前k 个数, k 远远小于n

使用排序算法进行全排序, 复杂度为O(nlogn)

使用二叉堆, 可以到O(nlogk)

过程:

1. 新建一个小顶堆
2. 扫描n 个整数
   1. 先将前k 个数放入堆中
   2. 从k + 1 开始, 如果大于堆ding,replace 操作
3. 扫描完成后, 堆中就是前k 的最大值

static void test3() {
        Integer[] data = {23, 60, 77, 21, 69, 15, 34, 93, 43, 65, 51, 28, 48, 33, 35, 10, 7, 80, 29, 86, 96, 8, 85, 66, 45, 40, 3, 78, 71, 11, 38, 16, 67, 50, 39, 91, 83, 37, 74, 97, 47, 1, 41, 44, 68, 36, 42, 6, 24};
        
        BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
            
        });
        
        int k = 5;
        int n = data.length;
        for (int i = 0; i < n; i++) {
            int value = data[i];
            if (heap.size() < k) {
                heap.add(value);
            } else if (value > heap.get()) {
                heap.replace(value);
            }
        }
        
        BinaryTrees.println(heap);
        
    }

优先级队列

普通队列, FIFO 原则, 优先级队列, 按照优先级进行出队, 将优先级最高的元素作为队头出队

例如, 医院的门诊, 病重的人优先级高, 操作系统的多任务调度, 任务类型优先级越高, 最先调度

public class PriorityQueue<E> {
    
    private BinaryHeap<E> heap = new BinaryHeap<>();
    
    public PriorityQueue(Comparator<E> comparator) {
        heap = new BinaryHeap<>(comparator);
    }
    
    public PriorityQueue() {
        this(null);
    }
    
    public int size() {
        return heap.size();
    }
    
    public boolean isEmpty() {
        return heap.isEmpty();
    }
    
    public void enQueue(E element) {
        heap.add(element);
    }
    
    public E deQueue() {
        return heap.remove();
    }
    
    public E front() {
        return heap.get();
    }
    
    public void clear() {
        heap.clear();
    }
}