优先级队列模拟实现

目录

1.堆的概念

2.堆性质堆中的某个元素小于或大于他的左右孩子

3.小根堆实例

4.堆创建

4.1调整思路

4.2向下调整思路

4.3代码实现（大根堆）

5.堆的删除

6.堆的插入

7.常用接口

7.1PriorityQueue和PriorityBlockingQueue

---

1.堆的概念

如果有一个关键码的集合K{k0,k1,k2,......kn},把他所有的元素按照二叉树的存储方式存储，在一个一维数组李，满足：ki<=2*ki-1且ki<2*ki-1+1,则称之为小根堆，反之称为大根堆。

2.堆性质
堆中的某个元素小于或大于他的左右孩子

堆是一个完全二叉树

3.小根堆实例

10

15

56

25

30

70

存储结构图

逻辑结构图

补充：

已知孩子节点是2*i+1 或者 2*i，则父亲节点是i

如果2*i+1大于数组长度则没有右孩子

如果i=0，则没有左右孩子，该节点是根节点

4.堆创建

向下调整：

27

15

19

18

28

34

65

49

25

37

4.1调整思路

从最后一颗数开始调整，每颗数都经过向下调整最终得到一个大根堆或者小根堆

4.2向下调整思路

1.首先让parent标记要调整的节点，child标记parent的左孩子（基于完全二叉树的性质，如果有孩子一定是先有左孩子）

2.如果parent的左孩子存在，即child<arr.length,在判断是否存在有孩子，如果存在判断右孩子是不是比左孩子大，若存在右孩子并且右孩子大于左孩子，则换成右孩子，最后将child和parent比较，如果要要构成大根堆：child大于parent则交换值，parent=child，child=parent*2+1继续向下调整;反之说明这颗树已经是一个大根堆的不需调整，进入下一个树的调整；如果要要构成小根堆：child小于于parent则交换值，parent=child，child=parent*2+1继续向下调整，反之说明这颗树已经是一个小根堆的不需调整，进入下一个树的调整；

根据实例得出的每一调整的顺序：

[27, 15, 19, 49, 37, 34, 65, 18, 25, 28]
[27, 15, 65, 49, 37, 34, 19, 18, 25, 28]
[27, 15, 65, 49, 37, 34, 19, 18, 25, 28]
[27, 49, 65, 25, 37, 34, 19, 18, 15, 28]
[27, 49, 65, 25, 37, 34, 19, 18, 15, 28]
[65, 49, 34, 25, 37, 27, 19, 18, 15, 28]
[65, 49, 34, 25, 37, 27, 19, 18, 15, 28]
[65, 49, 34, 25, 37, 27, 19, 18, 15, 28]

最终得到：

4.3代码实现（大根堆）

package sort;/*** @author starsea* @date 2024-06-24 13:02*/import com.sun.org.apache.bcel.internal.generic.SWAP;import java.util.Arrays;/*** 时间复杂度：O(N)* 空间复杂度：O(1)* 稳定性：不稳定*/
public class HeapSort {public static void main(String[] args) {int[] arr = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};createHeap(arr);}public static void createHeap(int[] arr) {int len = arr.length;for (int i = len - 1; i >= 0; i--) {int parent = (i - 1) / 2;siftDwon(arr, parent);System.out.println(Arrays.toString(arr));}}public static void siftDwon(int[] arr, int parent) {int child = parent * 2 + 1;while (child < arr.length) {if (child + 1 < arr.length && arr[child + 1] > arr[child]) {child++;}if (arr[parent] < arr[child]) {swap(arr, parent, child);parent = child;child = parent * 2 + 1;} else {break;}}}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}

5.堆的删除

1.从堆顶删除

思路：交换队尾和对堆头的元素，然后usedSize--，再次调整

package sort;/*** @author starsea* @date 2024-06-24 13:02*/import com.sun.org.apache.bcel.internal.generic.BranchHandle;
import com.sun.org.apache.bcel.internal.generic.SWAP;import java.util.Arrays;/*** 时间复杂度：O(N*log^N)* 空间复杂度：O(1)* 稳定性：不稳定*最后一位放的是删除元素*/
public class HeapSort {//删除堆头元素：1.交换堆头堆尾元素，2.usedsize减一3.再次调整public static void deleteElemt(int[] arr){int len=arr.length;swap(arr,0,len-1);for (int i = len-2; i >= 0; i--) {int parent = (i - 1) / 2;//siftDwon(arr, parent);siftUp(arr,i,len-2);// System.out.println("向下调整的每一步："+Arrays.toString(arr));System.out.println("删除调整的每一步："+Arrays.toString(arr));}}}

2.从堆尾删除

思路：直接usedSize--

6.堆的插入

思路放到尾巴上，然后向上调整

package sort;/*** @author starsea* @date 2024-06-24 13:02*/import com.sun.org.apache.bcel.internal.generic.BranchHandle;
import com.sun.org.apache.bcel.internal.generic.SWAP;import java.util.Arrays;/*** 时间复杂度：O(N*log^N)* 空间复杂度：O(1)* 稳定性：不稳定*/
public class HeapSort {public static void main(String[] args) {int[] arr = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};createHeap(arr,80);}public static void createHeap(int[] arr,int elemt) {int len = arr.length;//扩容arr=Arrays.copyOf(arr,arr.length*2);arr[len++]=elemt;for (int i = len-1; i >= 0; i--) {int parent = (i - 1) / 2;//siftDwon(arr, parent);siftUp(arr,i,len);// System.out.println("向下调整的每一步："+Arrays.toString(arr));System.out.println("向上调整的每一步："+Arrays.toString(arr));}}
//向下调整public static void siftDwon(int[] arr, int parent) {int child = parent * 2 + 1;while (child < arr.length) {if (child + 1 < arr.length && arr[child + 1] > arr[child]) {child++;}if (arr[parent] < arr[child]) {swap(arr, parent, child);parent = child;child = parent * 2 + 1;} else {break;}}}//向上调整public static void  siftUp(int[] arr,int child,int usedSize){int parent=(child-1)/2;while (child>0){if(child+1<usedSize && arr[child+1]>arr[child]){child++;}if(arr[child]>=arr[parent]){swap(arr,child,parent);child=parent;parent=(child-1)/2;}else{break;}}}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}

7.常用接口

7.1PriorityQueue和PriorityBlockingQueue

PriorityQueuey是线程不安全的而PriorityBlockingQueue是线程安全的。

7.2使用

//包
import java.util.PriorityQueue;riorityQueue<Integer> priorityQueue=new PriorityQueue<>();

注意：

1. 插入的对象必须是可比较的
2. 不能为空
3. 没有容量限制
4. 底层使用了堆
5. 默认是小根堆