二叉堆

如果要求实现一种数据结构, 用来添加元素、删除最大值、获取最大值，使用动态数组、双向链表会使删除或获取最大值达到O(n), 使用平衡二叉搜索树, 虽然各种操作能够用达到O(logn), 但显得有点大材小用

这时候, 堆这种数据结构就是一个更优的选择

获取最大是:O(1), 删除最大值: O(logn), 添加元素: O(logn)

最海量数据中找出前K个数据(Top K)问题也可以用堆解决

最大堆添加元素思路

检查数组是否需要扩容
将元素添加到数组的末尾
对数组的末尾元素进行上滤
上滤思路
- 如果node > 父节点, 交换位置
- 若果node <= 父节点, 或者没有父节点, 退出循环
- 优化: 不一定交换位置要真正的交换, 可以直接将父节点赋值到子节点中, 找到合适的索引后在存放node的值

实现代码
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size + 1);
elements[size++] = element;
siftUp(size - 1);
}

  private void siftUp(int index) {
      checkIndex(index);
      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;
  }

最大堆删除元素思路

将数组的最后一个元素覆盖第一个元素
将最后一个元素删除
对第一个元素进行下滤操作
下滤思路
- 循环执行以下操作
  - 如果node < 最大的子节点: 交换位置
  - 如果node >= 最大的子节点或者node没有子节点: 退出循环

实现代码
public E remove() {
checkEmpty();
E root = elements[0];
int lastIndex = --size;
elements[0] = elements[lastIndex];
elements[lastIndex] = null;
siftDown(0);
return root;
}

  private void siftDown(int index) {
      checkIndex(index);
      E element = elements[index];
      int half = size >> 1;
      while (index < half) {
          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;
  }

批量建堆的两种实现思路

自上而下的上滤: O(nlogn)
自下而上的下滤: O(n)
自下而上的下滤实现代码
public BinaryHeap(E[] elements, Comparator<E> comparator) {
this.comparator = comparator;
if (elements == null || elements.length == 0) {
this.elements = (E[])new Object[DEFAULT_CAPACITY];
} else {
int capacity = Math.max(DEFAULT_CAPACITY, elements.length);
this.elements = (E[])new Object[capacity];
size = elements.length;
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[i];
}
heapify(this.elements);
}
}
```
  private void heapify(E[] elements) {
      for (int i = (size >> 1) - 1; i >= 0; i--) {
          siftDown(i);
      }
  }
```

TopK问题

从n个整数中, 找出最大的前k个数(k << n)

实现思路: 二叉堆, O(logk)
- 新建一个最小堆
- 扫描n个整数
  - 先遍历的前k个数放入堆中
  - 从第k + 1个数开始, 如果大于堆顶元素, 就用此数进行replace操作
- 扫描完毕后, 堆中剩下的就是最大的前k个数
实现代码
public void topK() throws Exception {
Integer[] arr = new Integer[]{94, 67, 98, 95, 89, 92, 82, 11, 20, 100, 81};
BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
int top = 5;
for (int i = 0; i < arr.length; i++) {
if (i < top) {
heap.add(arr[i]);
} else if (arr[i] > heap.get()){
heap.replace(arr[i]);
}
}
}

如果是找出最小的前k个数, 则创建最大堆

二叉堆

二叉堆