赞
踩
目录
前面介绍的优先级队列在JDK1.8中其底层使用了堆的数据结构,而堆实际就是在完全二叉树的基础之上进行了一些元素的调整。
下面来看一下堆的可视化操作堆的可视化操作https://visualgo.net/zh/heap
- public void shiftDown(int[] array, int parent) {
- // child先标记parent的左孩子,因为parent可能右左没有右
- int child = 2 * parent + 1;
- int size = array.length;
- while (child < size) {
- // 如果右孩子存在,找到左右孩子中较小的孩子,用child进行标记
- if(child+1 < size && array[child+1] < array[child]){
- child += 1;
- }
-
- // 如果双亲比其最小的孩子还小,说明该结构已经满足堆的特性了
- if (array[parent] <= array[child]) {
- break;
- }else{
- // 将双亲与较小的孩子交换
- int t = array[parent];
- array[parent] = array[child];
- array[child] = t;
-
- // parent中大的元素往下移动,可能会造成子树不满足堆的性质,因此需要继续向下调整
- parent = child;
- child = parent * 2 + 1;
- }
- }
- }
- public static void createHeap(int[] array) {
- // 找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整
- for(int root = (array.length-2)/2; root >= 0; root--){
- shiftDown(array, array.length, root);
- }
- }
因此:建堆的时间复杂度为O(N)
- public void shiftUp(int child) {
- // 找到child的双亲
- int parent = (child - 1) / 2;
-
- while (child > 0) {
- // 如果双亲比孩子大,parent满足堆的性质,调整结束
- if (array[parent] > array[child]) {
- break;
- }else{
- // 将双亲与孩子节点进行交换
- int t = array[parent];
- array[parent] = array[child];
- array[child] = t;
-
- // 小的元素向下移动,可能到值子树不满足对的性质,因此需要继续向上调增
- child = parent;
- parent = (child - 1) / 2;
- }
- }
- }
- public static void shiftDown(int[] array, int size, int parent){
- int child = parent*2+1;
-
- while(child < size){
- // 找左右孩子中较大的孩子
- if(child+1 < size && array[child+1] > array[child]){
- child += 1;
- }
-
- // 双亲小于交大的孩子
- if(array[parent] < array[child]){
- swap(array, parent, child);
- parent = child;
- child = parent*2+1;
- }else{
- return;
- }
- }
- }
- public class MyPriorityQueue {
- Integer[] array;
- int size; // 有效元素的个数
-
- public MyPriorityQueue(){
- array = new Integer[11];
- size = 0;
- }
-
- public MyPriorityQueue(int initCapacity){
- if(initCapacity < 1){
- throw new IllegalArgumentException("初始容量小于1");
- }
-
- array = new Integer[initCapacity];
- size = 0;
- }
-
- public MyPriorityQueue(Integer[] arr){
- // 1. 将arr中的元素拷贝到数组中
- array = new Integer[arr.length];
- for(int i = 0; i < arr.length; ++i){
- array[i] = arr[i];
- }
- size = arr.length;
-
- // 2. 找当前完全二叉树中倒数第一个叶子节点
- // 注意:倒数第一个叶子节点刚好是最后一个节点的双亲
- // 最后一个节点的编号size-1 倒数第一个非叶子节点的下标为(size-1-1)/2
- int lastLeafParent = (size-2)/2;
-
- // 3. 从倒数第一个叶子节点位置开始,一直到根节点的位置,使用向下调整
- for(int root = lastLeafParent; root >= 0; root--){
- shiftDown(root);
- }
- }
-
- boolean offer(Integer e){
- if(e == null){
- throw new NullPointerException("插入时候元素为null");
- }
-
- ensureCapacity();
-
- array[size++] = e;
-
- // 注意:当新元素插入之后,可能会破坏对的性质---需要向上调整
- shiftUp(size-1);
- return true;
- }
-
- // 将堆顶的元素删除掉
- public Integer poll(){
- if(isEmpty()){
- return null;
- }
-
- Integer ret = array[0];
-
- // 1. 将堆顶元素与堆中最后一个元素交换
- swap(0, size-1);
-
- // 2. 将堆中有效元素个数减少一个
- size--; // size -= 1;
-
- // 3. 将堆顶元素往下调整到合适位置
- shiftDown(0);
- return ret;
- }
-
- public int size(){
- return size;
- }
-
- public boolean isEmpty(){
- return size == 0;
- }
-
- public void clear(){
- size = 0;
- }
-
- // 功能:调整以parent为根的二叉树
- // 前提:必须要保证parent的左右子树已经满足堆的特性
- // 时间复杂度:O(logN)
- private void shiftDown(int parent){
- // 默认让child先标记左孩子---因为:parent可能有左没有右
- int child = parent*2 + 1;
-
- // while循环条件可以保证:parent的左孩子一定存在
- // 但是不能保证parent的右孩子是否存在
- while(child < size){
- // 1. 找到左右孩子中较小的孩子
- if(child+1 < size && array[child+1] < array[child]){
- child += 1;
- }
-
- // 2. 较小的孩子已经找到了
- // 检测双亲和孩子间是否满足堆的特性
- if(array[parent] > array[child]){
- swap(parent, child);
-
- // 大的双亲往下走了,可能会导致子树又不满足堆的特性
- // 因此需要继续往下调整
- parent = child;
- child = parent*2 + 1;
- }else{
- // 以parent为根的二叉树已经是堆了
- return;
- }
- }
- }
-
- private void shiftUp(int child){
- int parent = (child-1)/2;
-
- while(child != 0){
- if(array[child] < array[parent]){
- swap(child, parent);
- child = parent;
- parent = (child-1)/2;
- }else{
- return;
- }
- }
- }
-
- private void ensureCapacity(){
- if(array.length == size){
- int newCapacity = array.length*2;
- array = Arrays.copyOf(array, newCapacity);
- }
- }
-
- // 注意:left和right是数组的下标
- private void swap(int left, int right){
- int temp = array[left];
- array[left] = array[right];
- array[right] = temp;
- }
- public static void swap(int[] array, int left, int right){
- int temp = array[left];
- array[left] = array[right];
- array[right] = temp;
- }
-
- public static void shiftDown(int[] array, int size, int parent){
- int child = parent*2+1;
-
- while(child < size){
- // 找左右孩子中较大的孩子
- if(child+1 < size && array[child+1] > array[child]){
- child += 1;
- }
-
- // 双亲小于交大的孩子
- if(array[parent] < array[child]){
- swap(array, parent, child);
- parent = child;
- child = parent*2+1;
- }else{
- return;
- }
- }
- }
-
- // 假设:升序
- public static void heapSort(int[] array){
- // 1. 建堆----升序:大堆 降序:小堆---向下调整
- for(int root = (array.length-2)/2; root >= 0; root--){
- shiftDown(array, array.length, root);
- }
-
-
- // 2. 利用堆删除的思想来排序---向下调整
- int end = array.length-1; // end标记最后一个元素
- while(end != 0){
- swap(array,0,end);
- shiftDown(array, end,0);
- end--;
- }
- }
- class Solution {
- public int[] smallestK(int[] arr, int k) {
- int[] vec = new int[k];
- if (k == 0) { // 排除 0 的情况
- return vec;
- }
- PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
- public int compare(Integer num1, Integer num2) {
- return num2 - num1;
- }
- });
- for (int i = 0; i < k; ++i) {
- queue.offer(arr[i]);
- }
- for (int i = k; i < arr.length; ++i) {
- if (queue.peek() > arr[i]) {
- queue.poll();
- queue.offer(arr[i]);
- }
- }
- for (int i = 0; i < k; ++i) {
- vec[i] = queue.poll();
- }
- return vec;
- }
- }
复杂度分析
时间复杂度:O(nlog k),其中 n 是数组 arr 的长度。由于大根堆实时维护前 k 小值,所以插入删除都是O(logk) 的时间复杂度,最坏情况下数组里 n 个数都会插入,所以一共需要 O(nlogk) 的时间复杂度。
空间复杂度:O(k),因为大根堆里最多 k 个数
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。