上海营销型网站开发,网站主机推荐,电子商务网站建设方案设计报告,游戏推广文案目录 1.堆的概念
2.堆性质堆中的某个元素小于或大于他的左右孩子
3.小根堆实例
4.堆创建
4.1调整思路
4.2向下调整思路
4.3代码实现#xff08;大根堆#xff09;
5.堆的删除
6.堆的插入
7.常用接口
7.1PriorityQueue和PriorityBlockingQueue 1.堆的概念
如果有一…目录 1.堆的概念
2.堆性质堆中的某个元素小于或大于他的左右孩子
3.小根堆实例
4.堆创建
4.1调整思路
4.2向下调整思路
4.3代码实现大根堆
5.堆的删除
6.堆的插入
7.常用接口
7.1PriorityQueue和PriorityBlockingQueue 1.堆的概念
如果有一个关键码的集合K{k0,k1,k2,......kn},把他所有的元素按照二叉树的存储方式存储在一个一维数组李满足ki2*ki-1且ki2*ki-11,则称之为小根堆反之称为大根堆。
2.堆性质 堆中的某个元素小于或大于他的左右孩子
堆是一个完全二叉树
3.小根堆实例 101556253070
存储结构图 逻辑结构图 补充 已知孩子节点是2*i1 或者 2*i则父亲节点是i 如果2*i1大于数组长度则没有右孩子 如果i0则没有左右孩子该节点是根节点 4.堆创建
向下调整
27151918283465492537 4.1调整思路
从最后一颗数开始调整每颗数都经过向下调整最终得到一个大根堆或者小根堆
4.2向下调整思路
1.首先让parent标记要调整的节点child标记parent的左孩子基于完全二叉树的性质如果有孩子一定是先有左孩子
2.如果parent的左孩子存在即childarr.length,在判断是否存在有孩子如果存在判断右孩子是不是比左孩子大若存在右孩子并且右孩子大于左孩子则换成右孩子最后将child和parent比较如果要要构成大根堆child大于parent则交换值parentchildchildparent*21继续向下调整;反之说明这颗树已经是一个大根堆的不需调整进入下一个树的调整如果要要构成小根堆child小于于parent则交换值parentchildchildparent*21继续向下调整反之说明这颗树已经是一个小根堆的不需调整进入下一个树的调整
根据实例得出的每一调整的顺序
[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 lenarr.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;//扩容arrArrays.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 (child0){if(child1usedSize arr[child1]arr[child]){child;}if(arr[child]arr[parent]){swap(arr,child,parent);childparent;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;riorityQueueInteger priorityQueuenew PriorityQueue(); 注意 插入的对象必须是可比较的不能为空没有容量限制底层使用了堆默认是小根堆
