眼睛网站开发,wordpress全站cdn ssl,厦门 网站建设 网站开发,中国建设官方网站企业在学习本节文章前要先了解#xff1a;大顶堆与小顶堆#xff1a; #xff08;优先级队列_加瓦不加班的博客-CSDN博客#xff09;
堆实现
计算机科学中#xff0c;堆是一种基于树的数据结构#xff0c;通常用完全二叉树实现。
什么叫完全二叉树#xff1f;
答#x…在学习本节文章前要先了解大顶堆与小顶堆 优先级队列_加瓦不加班的博客-CSDN博客
堆实现
计算机科学中堆是一种基于树的数据结构通常用完全二叉树实现。
什么叫完全二叉树
答 1.除了最后一层不用满足有两个分支其他层都要满足有两个分支 2.如果再往完全二叉树中加一个节点那么必须靠左添加从左往右依次填满左边没有填满之前右边就不能填如图 添加前 添加后 堆的特性如下堆分为两种大顶堆与小顶堆 在大顶堆中任意节点 C 与它的父节点 P 符合 P.value C.value父节点的值子节点的值 而小顶堆中任意节点 C 与它的父节点 P 符合 P.value C.value父节点的值子节点的值 最顶层的节点没有父亲称之为 root 根节点 例1 - 满二叉树Full Binary Tree特点每一层都是填满的 例2 - 完全二叉树Complete Binary Tree特点最后一层可能未填满靠左对齐 大顶堆 大顶堆中任意节点 C 与它的父节点 P 符合 P.value C.value父节点的值子节点的值 代码实现 /*** BelongsProject: arithmetic* BelongsPackage: com.hzp.algorithm.heap* Author: ASUS* CreateTime: 2023-10-02 10:41* Description: TODO 大顶堆Plus_增加了堆化等方法* Version: 1.0*/
public class MaxHeap {int[] array;int size;public MaxHeap(int capacity) {this.array new int[capacity];}/*** 获取堆顶元素** return 堆顶元素*/public int peek() {//注意:当传入的数组是null时我们可以设置一个判断来抛个异常在这里我们就不去判断请有需要的自行return array[0];}/*** 删除堆顶元素** return 堆顶元素*/public int poll() {//注意:当传入的数组是null,可以设置一个判断来抛个异常在这里我们就不去判断请有需要的自行if(isEmpty()){throw new IllegalArgumentException(数组有问题);}int top array[0];swap(0, size - 1);size--;//从索引位置0开始下潜down(0);return top;}private boolean isEmpty(){if(size0){return true;}return false;}/*** 删除指定索引处元素 这个方法与删除堆顶元素方法思路一样** param index 索引* return 被删除元素*/public int poll(int index) {//注意:当传入的数组是null,可以设置一个判断来抛个异常在这里我们就不去判断请有需要的自行if(isEmpty()){throw new IllegalArgumentException(数组有问题);}int deleted array[index];swap(index, size - 1);size--;down(index);return deleted;}/*** 替换堆顶元素* param replaced 新元素*/public void replace(int replaced) {array[0] replaced;down(0);}/*** 堆的尾部添加元素** param offered 新元素* return 是否添加成功*/public boolean offer(int offered) {if (size array.length) {return false;}up(offered);size;return true;}//向堆的尾部添加元素 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered) {int child size;while (child 0) {int parent (child - 1) / 2;if (offered array[parent]) {array[child] array[parent];} else {break;}child parent;}array[child] offered;}public MaxHeap(int[] array) {this.array array;this.size array.length;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点 套用公式 size / 2 - 1for (int i size / 2 - 1; i 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left parent * 2 1;int right left 1;int max parent;//left size:必须是有效的索引 不可能超出数组最大长度吧if (left size array[left] array[max]) {max left;}if (right size array[right] array[max]) {max right;}if (max ! parent) { // 找到了更大的孩子swap(max, parent);down(max);}}// 交换两个索引处的元素private void swap(int i, int j) {int t array[i];array[i] array[j];array[j] t;}public static void main(String[] args) {
// int[] array {1, 2, 3, 4, 5, 6, 7};
// MaxHeap maxHeap new MaxHeap(array);
// System.out.println(Arrays.toString(maxHeap.array));//TODO 利用堆来实现排序//1. heapify 建立大顶堆//2. 将堆顶与堆底交换最大元素被交换到堆底缩小并下潜调整堆//3. 重复第二步直至堆里剩一个元素int[] array {1, 2, 3, 4, 5, 6, 7};//1. heapify 建立大顶堆MaxHeap maxHeap new MaxHeap(array);System.out.println(Arrays.toString(maxHeap.array));//3. 重复第二步直至堆里剩一个元素while(maxHeap.size1){//将堆顶与堆底交换最大元素被交换到堆底缩小并下潜调整堆maxHeap.swap(0, maxHeap.size-1);maxHeap.size--;maxHeap.down(0);}System.out.println(Arrays.toString(maxHeap.array));}
}小顶堆 小顶堆中任意节点 C 与它的父节点 P 符合 P.value C.value父节点的值子节点的值 代码实现
/*** BelongsProject: arithmetic* BelongsPackage: com.hzp.algorithm.heap* Author: ASUS* CreateTime: 2023-10-02 10:41* Description: TODO 小顶堆Plus_增加了堆化等方法* Version: 1.0*/
public class MinHeap {int[] array;int size;public MinHeap(int capacity) {this.array new int[capacity];}/*** 获取堆顶元素** return 堆顶元素*/public int peek() {//注意:当传入的数组是null时我们可以设置一个判断来抛个异常在这里我们就不去判断请有需要的自行return array[0];}/*** 删除堆顶元素** return 堆顶元素*/public int poll() {//注意:当传入的数组是null,可以设置一个判断来抛个异常在这里我们就不去判断请有需要的自行if(isEmpty()){throw new IllegalArgumentException(数组有问题);}int top array[0];swap(0, size - 1);size--;//从索引位置0开始下潜down(0);return top;}private boolean isEmpty(){if(size0){return true;}return false;}public boolean isFull(){return sizearray.length;}/*** 删除指定索引处元素 这个方法与删除堆顶元素方法思路一样** param index 索引* return 被删除元素*/public int poll(int index) {//注意:当传入的数组是null,可以设置一个判断来抛个异常在这里我们就不去判断请有需要的自行if(isEmpty()){throw new IllegalArgumentException(数组有问题);}int deleted array[index];swap(index, size - 1);size--;down(index);return deleted;}/*** 替换堆顶元素* param replaced 新元素*/public void replace(int replaced) {array[0] replaced;down(0);}/*** 堆的尾部添加元素** param offered 新元素* return 是否添加成功*/public boolean offer(int offered) {if (size array.length) {return false;}up(offered);size;return true;}//向堆的尾部添加元素 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered) {int child size;while (child 0) {int parent (child - 1) / 2;if (offered array[parent]) {array[child] array[parent];} else {break;}child parent;}array[child] offered;}public MinHeap(int[] array) {this.array array;this.size array.length;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点 套用公式 size / 2 - 1for (int i size / 2 - 1; i 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left parent * 2 1;int right left 1;int min parent;//left size:必须是有效的索引 不可能超出数组最大长度吧if (left size array[left] array[min]) {min left;}if (right size array[right] array[min]) {min right;}if (min ! parent) { // 找到了更大的孩子swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t array[i];array[i] array[j];array[j] t;}public static void main(String[] args) {
// int[] array {1, 2, 3, 4, 5, 6, 7};
// MaxHeap maxHeap new MaxHeap(array);
// System.out.println(Arrays.toString(maxHeap.array));//1. heapify 建立小顶堆//2. 将堆顶与堆底交换最大元素被交换到堆底缩小并下潜调整堆//3. 重复第二步直至堆里剩一个元素int[] array {1, 2, 3, 4, 5, 6, 7};//1. heapify 建立大顶堆MinHeap maxHeap new MinHeap(array);System.out.println(Arrays.toString(maxHeap.array));//3. 重复第二步直至堆里剩一个元素while(maxHeap.size1){//将堆顶与堆底交换最大元素被交换到堆底缩小并下潜调整堆maxHeap.swap(0, maxHeap.size-1);maxHeap.size--;maxHeap.down(0);}System.out.println(Arrays.toString(maxHeap.array));}
}完全二叉树可以使用数组来表示 那完全二叉树显然是个非线性的数据结构但是它存储的时候可以使用线性的数组结构来存储数据 特征 如果从索引 0 开始存储节点数据 节点 i 的父节点为 floor((i-1)/2)当 i0 时 节点 i 的左子节点为 2i1右子节点为 2i2当然它们得 size 如果从索引 1 开始存储节点数据 节点 i 的父节点为 floor(i/2)当 i 1 时 节点 i 的左子节点为 2i右子节点为 2i1同样得 size 堆的优化
以大顶堆为例相对于之前的优先级队列增加了堆化等方法
public class MaxHeap {int[] array;int size;public MaxHeap(int capacity) {this.array new int[capacity];}/*** 获取堆顶元素** return 堆顶元素*/public int peek() {//注意:当传入的数组是null时我们可以设置一个判断来抛个异常在这里我们就不去判断请有需要的自行return array[0];}/*** 删除堆顶元素** return 堆顶元素*/public int poll() {//注意:当传入的数组是null,可以设置一个判断来抛个异常在这里我们就不去判断请有需要的自行int top array[0];swap(0, size - 1);size--;//从索引位置0开始下潜down(0);return top;}/*** 删除指定索引处元素 这个方法与删除堆顶元素方法思路一样** param index 索引* return 被删除元素*/public int poll(int index) {//注意:当传入的数组是null,可以设置一个判断来抛个异常在这里我们就不去判断请有需要的自行int deleted array[index];swap(index, size - 1);size--;down(index);return deleted;}/*** 替换堆顶元素* param replaced 新元素*/public void replace(int replaced) {array[0] replaced;down(0);}/*** 堆的尾部添加元素** param offered 新元素* return 是否添加成功*/public boolean offer(int offered) {if (size array.length) {return false;}up(offered);size;return true;}//向堆的尾部添加元素 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered) {int child size;while (child 0) {int parent (child - 1) / 2;if (offered array[parent]) {array[child] array[parent];} else {break;}child parent;}array[child] offered;}public MaxHeap(int[] array) {this.array array;this.size array.length;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点 套用公式 size / 2 - 1for (int i size / 2 - 1; i 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left parent * 2 1;int right left 1;int max parent;//left size:必须是有效的索引 不可能超出数组最大长度吧if (left size array[left] array[max]) {max left;}if (right size array[right] array[max]) {max right;}if (max ! parent) { // 找到了更大的孩子swap(max, parent);down(max);}}// 交换两个索引处的元素private void swap(int i, int j) {int t array[i];array[i] array[j];array[j] t;}public static void main(String[] args) {int[] array {1, 2, 3, 4, 5, 6, 7};MaxHeap maxHeap new MaxHeap(array);System.out.println(Arrays.toString(maxHeap.array));}
} Floyd 建堆算法作者也是之前龟兔赛跑判环作者
如果对龟兔赛跑判环不了解的可以查看此文章 找到最后一个非叶子节点 叶子节点没有孩子的节点 从后向前对每个节点执行下潜
一些规律 一棵满二叉树节点个数为 2^h-1如下例中高度 h3 节点数是 2^3-17 非叶子节点范围为 [0, size/2-1]
算法时间复杂度分析 下面看交换次数的推导设节点高度为 3 每一层的交换次数为节点个数*此节点交换次数总的交换次数为 即 h:总高度 i:本层高度 在 Wolfram|Alpha: Computational Intelligence 输入 Sum[\(40)Divide[Power[2,x],Power[2,i]]*\(40)i-1\(41)\(41),{i,1,x}] 推导出 通用堆
通用heap :可以扩容的 heap, max 用于指定是大顶堆还是小顶堆
/*** BelongsProject: arithmetic* BelongsPackage: com.hzp.algorithm.heap* Author: ASUS* CreateTime: 2023-10-02 15:56* Description: TODO 通用heap :可以扩容的 heap, max 用于指定是大顶堆还是小顶堆* Version: 1.0*/
public class Heap {int[] array;int size;boolean max;public int size() {return size;}//当max为true则为大顶堆 如果是false则为小顶堆public Heap(int capacity, boolean max) {this.array new int[capacity];this.max max;}/*** 获取堆顶元素** return 堆顶元素*/public int peek() {return array[0];}/*** 删除堆顶元素** return 堆顶元素*/public int poll() {int top array[0];swap(0, size - 1);size--;down(0);return top;}/*** 删除指定索引处元素** param index 索引* return 被删除元素*/public int poll(int index) {int deleted array[index];swap(index, size - 1);size--;down(index);return deleted;}/*** 替换堆顶元素** param replaced 新元素*/public void replace(int replaced) {array[0] replaced;down(0);}/*** 堆的尾部添加元素** param offered 新元素*/public void offer(int offered) {if (size array.length) {grow();}up(offered);size;}//如果容量不够就进行扩容private void grow() {int capacity size (size 1);int[] newArray new int[capacity];//将原有的数组重新放到扩容好的数组中System.arraycopy(array, 0,newArray, 0, size);array newArray;}// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered) {int child size;while (child 0) {int parent (child - 1) / 2;boolean cmp max ? offered array[parent] : offered array[parent];if (cmp) {array[child] array[parent];} else {break;}child parent;}array[child] offered;}public Heap(int[] array, boolean max) {this.array array;this.size array.length;this.max max;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点 size / 2 - 1for (int i size / 2 - 1; i 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left parent * 2 1;int right left 1;int min parent;if (left size (max ? array[left] array[min] : array[left] array[min])) {min left;}if (right size (max ? array[right] array[min] : array[right] array[min])) {min right;}if (min ! parent) { // 找到了更大的孩子swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t array[i];array[i] array[j];array[j] t;}}
