源代码如何做网站,app官网登录入口,北京制作网站的基本流程,什么是ui界面算法描述 heapify 建立大顶堆 将堆顶与堆底交换#xff08;最大元素被交换到堆底#xff09;#xff0c;缩小并下潜调整堆 重复第二步直至堆里剩一个元素 可以使用之前课堂例题的大顶堆#xff08;堆的初步认识-CSDN博客#xff09;来实现
MaxHeap方法#xff1a;
/…算法描述 heapify 建立大顶堆 将堆顶与堆底交换最大元素被交换到堆底缩小并下潜调整堆 重复第二步直至堆里剩一个元素 可以使用之前课堂例题的大顶堆堆的初步认识-CSDN博客来实现
MaxHeap方法
/*** 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));}
} 实现
int[] array {1, 2, 3, 4, 5, 6, 7};
MaxHeap maxHeap new MaxHeap(array);
System.out.println(Arrays.toString(maxHeap.array));while (maxHeap.size 1) {maxHeap.swap(0, maxHeap.size - 1);maxHeap.size--;maxHeap.down(0);
}
System.out.println(Arrays.toString(maxHeap.array));
