堆排序-建堆，增删替换

我们 之前写过根据 堆排序的优先级队列，但是如果我们想要建立一个堆怎么办呢？ 如何实现上浮 下潜 具体看这篇文章

堆排序-优先级队列-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(size==0){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(size>1) {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();}
}

测试结果如下