堆
1. 定义
底层: 完全二叉树大根堆: 任意树头结点是这棵树的最大值小根堆: 任意树头结点是这棵树的最小值
2. 构造大根堆:
public static class MyMaxHeap {
private int[] heap;
private final int limit;
private int heapSize;
public MyMaxHeap(int limit) {
heap = new int[limit];
this.limit = limit;
heapSize = 0;
}
public boolean isEmpty() {
return heapSize == 0;
}
public boolean isFull() {
return heapSize == limit;
}
public void push(int value) {
if (heapSize == limit) {
throw new RuntimeException("heap is full");
}
heap[heapSize] = value;
// value heapSize
heapInsert(heap, heapSize++);
}
// 用户此时，让你返回最大值，并且在大根堆中，把最大值删掉
// 剩下的数，依然保持大根堆组织
public int pop() {
int ans = heap[0];
swap(heap, 0, --heapSize);
heapify(heap, 0, heapSize);
return ans;
}
// 新加进来的数，现在停在了index位置，请依次往上移动，
// 移动到0位置，或者干不掉自己的父亲了，停！
private void heapInsert(int[] arr, int index) {
// [index] [index-1]/2
// index == 0
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
// 从index位置，往下看，不断的下沉
// 停：较大的孩子都不再比index位置的数大；已经没孩子了
private void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1;
while (left < heapSize) { // 如果有左孩子，有没有右孩子，可能有可能没有！
// 把较大孩子的下标，给largest
// 右 -> 1)有右孩子 && 2)右孩子的值比左孩子大才行
// 否则 左
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
// 两个孩子较大值跟父节点进行比较
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
// index和较大孩子，要互换
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
3. 系统堆
public static void main(String[] args) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(5);
heap.add(4);
heap.add(7);
heap.add(9);
heap.add(2);
while (!heap.isEmpty()) {
System.out.println(heap.poll());
}
}
4. 比较器
- 比较器的实质就是重载比较运算符
- 比较器可以很好的运用在特殊标准的排序上
- 比较器可以很好的引用再根据特殊标准结构的排序上
- 写代码变得异常容易,还被用于泛型编程
// 大根堆
public static class MyComp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
public static void main(String[] args) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>(new MyComp());
heap.add(5);
heap.add(8);
heap.add(6);
heap.add(7);
heap.add(2);
heap.add(3);
heap.add(0);
while (!heap.isEmpty()) {
System.out.println(heap.poll());
}
}
5. 堆的reset方法
/*
* T一定要是非基础类型，有基础类型需求包一层
*/
public class HeapGreater<T> {
// 用ArrayList存储带有泛型的动态数组,因为普通数组不能带泛型
private ArrayList<T> heap;
// 一个反向表
private HashMap<T, Integer> indexMap;
// 存储堆大小的指针
private int heapSize;
// 自定义比较器
private Comparator<? super T> comp;
// 构造器
public HeapGreater(Comparator<T> c) {
heap = new ArrayList<>();
indexMap = new HashMap<>();
// 堆大小初始化为0
heapSize = 0;
comp = c;
}
public boolean isEmpty() {
return heapSize == 0;
}
public int size() {
return heapSize;
}
public boolean contains(T obj) {
return indexMap.containsKey(obj);
}
public T peek() {
return heap.get(0);
}
// 添加一个数
public void push(T obj) {
// heap直接接受这个数add到最后
heap.add(obj);
// 在mao表中添加
indexMap.put(obj, heapSize);
heapInsert(heapSize++);
}
public T pop() {
// ans存储结果heap 0位置的元素
T ans = heap.get(0);
// 交换0位置和最后一个位置的元素
swap(0, heapSize - 1);
// 移除map表中 ans值的数据
indexMap.remove(ans);
// 移除堆中最后一个位置上的元素
heap.remove(--heapSize);
// 从0位置开始调整堆
heapify(0);
return ans;
}
public void remove(T obj) {
T replace = heap.get(heapSize - 1);
int index = indexMap.get(obj);
indexMap.remove(obj);
heap.remove(--heapSize);
if (obj != replace) {
heap.set(index, replace);
indexMap.put(replace, index);
resign(replace);
}
}
// 重新调整堆(当有堆中值的变化时候调用)
public void resign(T obj) {
// 直接通过map找到要调整节点的位置
// 向上移动
heapInsert(indexMap.get(obj));
// 或者向下移动(只会执行一个)
heapify(indexMap.get(obj));
}
// 请返回堆上的所有元素
public List<T> getAllElements() {
List<T> ans = new ArrayList<>();
for (T c : heap) {
ans.add(c);
}
return ans;
}
private void heapInsert(int index) {
// 调用比较器,知道index和index的父节点怎么比大小
while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
// 交换index和父节点
swap(index, (index - 1) / 2);
// 变换index的值到父节点
index = (index - 1) / 2;
}
}
private void heapify(int index) {
// 从index位置找到left的下标
int left = index * 2 + 1;
// 根据比较器比较大小并换位
while (left < heapSize) {
int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
if (best == index) {
break;
}
swap(best, index);
index = best;
left = index * 2 + 1;
}
}
// 交换heap中的元素的时候要同时变换map中的元素
// 保持heap和map的高度同步
private void swap(int i, int j) {
T o1 = heap.get(i);
T o2 = heap.get(j);
heap.set(i, o2);
heap.set(j, o1);
indexMap.put(o2, i);
indexMap.put(o1, j);
}
}
时间复杂度O(logN)
思考
从下往上建堆和从上往下建堆有什么不一样
从上往下 : heapinsert 往上看有大的就往上换 (直观上:代价从上往下依次变大)
从下往上: heapify 往下看 有小的就往下沉 (直观上: 代价从下往上 依次变大 )
堆有关题目
- 有一个几乎有序的数组.几乎有序是指,如果把数组排好序的话,每个元素移动的距离一定不超过k,并且k相对于数组长度来说是比较小的.请选择一个适合的排序策略,对这个数组进行排序.
public static void sortedArrDistanceLessK(int[] arr, int k) {
if (k == 0) {
return;
}
// 默认小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0;
// 0...K-1
for (; index <= Math.min(arr.length - 1, k - 1); index++) {
heap.add(arr[index]);
}
int i = 0;
for (; index < arr.length; i++, index++) {
heap.add(arr[index]);
arr[i] = heap.poll();
}
while (!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}
若有收获，就点个赞吧
0 人点赞
