wordpress修改地址后网站打不开,免费邯郸网站建设,外贸网站有哪些平台,电影院做羞羞的网站我们 之前写过根据 堆排序的优先级队列#xff0c;但是如果我们想要建立一个堆怎么办呢#xff1f; 如何实现上浮 下潜 具体看这篇文章
堆排序-优先级队列-CSDN博客
建堆
我们有两种方法建立一个堆
1.我们基于add方法建立一个堆#xff0c;一次次的add#xff0c;然后对…我们 之前写过根据 堆排序的优先级队列但是如果我们想要建立一个堆怎么办呢 如何实现上浮 下潜 具体看这篇文章
堆排序-优先级队列-CSDN博客
建堆
我们有两种方法建立一个堆
1.我们基于add方法建立一个堆一次次的add然后对元素进行一次次的上浮操作达成堆排序
2. 直接基于一个现成的数组建立一个堆然后我们根据这个现成的数组进行建立堆
基于这两种方法我们提供了两个构造方法 堆排序的实现
我们直接把堆中的元素根据删除原理进行排序 就能实现把一个堆进行排序了
就比如 把最大的也就是堆顶的元素 跟最小的元素交换 然后下潜一直重复这个操作直到最小的元素在数组的索引0位置即可 下面来看完整源码
package heap.maxheap;import java.util.Arrays;public class MaxHeap {int[] array;//堆数组int size;//元素个数public MaxHeap(int capacity) {array new int[capacity];}public MaxHeap(int[] arr) {array arr;size array.length;heap();}/*** 建堆方法*/private void heap() {//建堆 需要找到 叶子节点的父节点最后一个元素的索引位置 父节点//从父节点 开始 依次进行建堆操作//值得注意的是 我们建堆 找到的 是元素的索引位置// 是根据 arr.length 也就是size 来进行 寻找的//我们找到 叶子节点、父节点的索引位置 也就是下潜操作中 是根据 索引位置来寻找的for (int i size / 2 - 1; i 0; i--) {down(i);}}private void down(int parent) {int left parent * 2 1;int right left 1;int max parent;while (true) {if (left size array[left] array[max]) {max left;}if (right size array[right] array[max]) {max right;}if (max parent) {break;}swap(parent, max);parent max;left parent * 2 1;right left 1;}}public void up(int index) {int child index;int parent (child - 1) / 2;//继续上浮的条件应该是 父节点 变成根节点while (parent 0) {if (array[parent] array[child]) {swap(parent, child);child parent;parent (child - 1) / 2;}else {break;}}}public Boolean add(int element) {if (size array.length) {return false;}array[size] element;up(size);size;return true;}/*** return int* 删除堆顶的元素* 删除元素的时候 数组查找删除比较慢 我们直接* 把数组尾部 跟 堆顶的元素 交换删除 然后下潜*/public int poll() {//此处应有非空判断我不想写了if(size0){throw new IllegalArgumentException(元素为0 无法删除);}int temp array[0];swap(0, size - 1);size--;down(0);return temp;}/*** param index 要删除 指定元素的索引* return int*/public int poll(int index) {if (index 0 || index size - 1) {throw new IllegalArgumentException(索引位置错误);}int i array[index];array[index]-1;swap(index,size-1);size--;down(index);return i ;}private void swap(int i, int j) {int temp array[i];array[i] array[j];array[j] temp;}//堆排序 怎么实现堆排序 我们只需要 拿到堆顶的最大的元素 就行了public void heapSort(){while(size1) {swap(0,size-1);size--;down(0);}System.out.println(Arrays.toString(array));}}测试案例 如下
package heap.maxheap;import java.util.Arrays;public class MaxHeapTest {public static void main(String[] args) {MaxHeap maxHeap new MaxHeap(5);maxHeap.add(1);maxHeap.add(3);maxHeap.add(6);maxHeap.add(5);maxHeap.add(2);int[] array maxHeap.array;System.out.println(Arrays.toString(array));System.out.println(--------------);int[] ints {1,2,3,4,5,6,7};MaxHeap maxHeap1 new MaxHeap(ints);System.out.println(Arrays.toString(maxHeap1.array));int poll1 maxHeap1.poll(0);System.out.println(Arrays.toString(maxHeap1.array));maxHeap1.heapSort();}
}测试结果如下
