堆
堆的实现
public class MaxHeap{int[] array;int size;public MaxHeap(int capacity) {this.array = new int[capacity];}public MaxHeap(int[] array) {this.array = array;this.size = array.length;heapify();}// 建堆操作-----重点public void heapify() {// 1. 找到最后一个非叶子节点 size / 2 - 1;for(int i = size / 2 - 1; i >= 0; i--) {// 下潜操作down(i);}}// 下潜操作-----重点private void down(int parent) {int left = parent * 2 + 1;int right = left + 1;int max = parent;if (left < size && array[left] > array[parent]) {max = left;}if (right < size && array[right] > array[parent]) {max = right;}if (max != parent) {swap(max, parent);down(max);}}private void swap(int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}// 获取顶部元素public int peek() {return array[0];}// 删除堆顶元素public int poll(){int value = array[0];swap(0, size - 1);size--;down(0);return value;}// 删除指定索引的元素public int poll(int index) {int value = array[index];swap(index, size - 1);size--;down(index);return value;}// 替换堆顶元素public void replace(int replaced) {array[0] = replaced;down(0);}// 尾部添加元素public boolean offer(int value) {if(size == array.length) {return false;} up(value);size++;}// 上浮操作-----重点public void up(int value) {int child = size;while (child > 0) {int parent = (child - 1) / 2;if (value > array[parent]) {array[child] = array[parent];} else {break;}parent = child;}array[child] = value;}
}
堆的应用
堆排序
pubic static void main(String[] args) {int[] array = new int[]{2, 3, 1, 7, 6, 4, 5};MaxHeap heap = new MaxHeap(array);System.out.println(Array.toString(heap.array));while (heap.size > 1) {heap.swap(0, size - 1);size--;down(0);}// 打印输出排序后的数组System.out.println(Array.toString(heap.array));
}
Leetcode215
求数组中第k大元素，使用小顶堆完成
- 向小顶堆放入k个元素
- 剩余元素
- 若<= 堆顶元素，则略过；
- 若>堆顶元素，则替换堆顶元素
- 这样小顶堆始终保持前k大元素；
- 循环结束，堆顶元素即为数组第k大元素；
public class MinHeap{int[] array;int size;public MinHeap(int capacity) {this.array = new int[capacity];}public MinHeap(int[] array) {this.array = array;this.size = array.length;heapify();}// 建堆操作-----重点public void heapify() {// 1. 找到最后一个非叶子节点 size / 2 - 1;for(int i = size / 2 - 1; i >= 0; i--) {// 下潜操作down(i);}}// 下潜操作-----重点private void down(int parent) {int left = parent * 2 + 1;int right = left + 1;int min = parent;if (left < size && array[left] < array[parent]) {min = left;}if (right < size && array[right] < array[parent]) {min = right;}if (max != parent) {swap(min, parent);down(min);}}private void swap(int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}// 获取顶部元素public int peek() {return array[0];}// 替换堆顶元素public void replace(int replaced) {array[0] = replaced;down(0);}// 尾部添加元素public boolean offer(int value) {if(size == array.length) {return false;} up(value);size++;}// 上浮操作-----重点public void up(int value) {int child = size;while (child > 0) {int parent = (child - 1) / 2;if (value < array[parent]) {array[child] = array[parent];} else {break;}parent = child;}array[child] = value;}public boolean isFull() {return size == array.length;}
}
public class Leetcode215{public int findKthLargeest(int[] numbers, int k) {MinHeap heap = new MinHeap(k);for(int i = 0; i < k; i++) {heap.offer(numbers[i]);}for(int i = k; i < numbers.length; i++) {if (numbers[i] > heap.peek()) {heap.replace(numbers[i]);}}return heap.peek();}public static void main(String[] args) {int[] array = {3, 2, 1, 5, 6, 4}; System.out.println(new Leetcode215().findKthLargest(array, 2));}
}Leetcode703
求数据流中的第K大元素
public class Leetcode703{// 成员变量private MinHeap heap;public Leetcode703(int k, int[] nums) {heap = new MinHeap(k);for(int num : nums) {add(num);}}public int add(int val) {if (!heap.isFull()) {heap.offer(val);} else {if (val > heap.peek()) {heap.replace(val);}}return heap.peek();}public static void main(String[] args) {Leetcode703 test = new Leetcode703(3, new int[]{4, 5, 8, 2});test.add(3);test.add(5);test.add(10);test.add(9);test.add(4);}
}
Leetcode295
求数据流中的中位数
实现堆
将大顶堆和小顶堆代码合并，通过max设置true或false生成大顶堆和小顶堆
public class Heap {int[] array;int size;boolean max;public Heap(int capacity, boolean max) {this.array = new int[capacity];this.max = max; // max=true 大顶堆，max=false，小顶堆}public Heap(int[] array) {this.array = array;this.size = array.length;heapify();}public int peek() {if (size == 0) {throw new IllegalArgumentException("heap is empty");}return array[0];}public int poll() {int top = array[0];swap(0, size - 1);size--;down(0);return top;}public int poll(int index) {int value = array[index];swap(index, size - 1);size--;down(index);return value;}// 替换堆顶的元素public void replace(int value) {array[0] = value;down(0);}// 堆的尾部添加元素public boolean offer(int value) {if (size == array.length) {return false;}up(value);size++;return true;}private void up(int value) {int child = size;while (child > 0) {int parent = (child - 1) / 2;// cmp为真，则为大顶堆，否则为小顶堆boolean cmp = max ? value > array[parent] : value < array[parent];if (cmp) {array[child] = array[parent];} else {break;}child = parent;}array[child] = value;}//建堆private void heapify() {for (int i = (size >>> 1) - 1; i >= 0; i--) {down(i);}}public void down(int parent) {int left = parent * 2 + 1;int right = left + 1;int minOrMax = parent;if (left < size && (max ? array[left] > array[minOrMax] : array[left] < array[minOrMax])) {minOrMax = left;}if (right < size && (max ? array[right] > array[minOrMax] : array[right] < array[minOrMax])){minOrMax = right;}if (minOrMax != parent) {swap(parent, minOrMax);down(minOrMax);}}private void swap(int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}public boolean isFull() {return size == array.length;}
}
代码实现过程
为了保证两边数据量的平衡
- 两边个数相等时，向左边添加元素
- 左边个数加一时，先向右边添加元素后，将右边堆顶元素移除并添加到左边
- 两边个数不相等时，右边个数加一
- 右边个数加一时，先向左边添加元素后，将左侧堆顶元素移除并添加到右边
public class Leetcode295{private heap left = new heap((10, true); //左侧大顶堆private heap right = new heap(10, false); //右侧小顶堆public int addNum(int num) {if(left.getSize() == right.getSize()) {right.offer(num);left.offer(right.poll());} else {left.offer(num);right.offer(left.poll());}}public double findMedian() {if (left.getSize() == right.getSize()) {// 偶数个数return (left.peek() + right.peek()) / 2.0;} else {// 奇数个数return left.peek();}}
}
使用优先级队列实现
public class Leetcode295{private heap left = new heap((10, true); //左侧大顶堆private heap right = new heap(10, false); //右侧小顶堆public int addNum(int num) {if(left.getSize() == right.getSize()) {right.offer(num);left.offer(right.poll());} else {left.offer(num);right.offer(left.poll());}}public double findMedian() {if (left.getSize() == right.getSize()) {// 偶数个数return (left.peek() + right.peek()) / 2.0;} else {// 奇数个数return left.peek();}}private PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> Integer.compare(b, a)); //da'dprivate PriorityQueue<Integer> right = new PriorityQueue<>(); // 默认小顶堆
}