我們 之前寫(xiě)過(guò)根據(jù) 堆排序的優(yōu)先級(jí)隊(duì)列，但是如果我們想要建立一個(gè)堆怎么辦呢？ 如何實(shí)現(xiàn)上浮 下潛 具體看這篇文章

堆排序-優(yōu)先級(jí)隊(duì)列-CSDN博客

建堆

我們有兩種方法建立一個(gè)堆

1.我們基于add方法建立一個(gè)堆，一次次的add，然后對(duì)元素進(jìn)行一次次的上浮操作，達(dá)成堆排序

2. 直接基于一個(gè)現(xiàn)成的數(shù)組建立一個(gè)堆，然后我們根據(jù)這個(gè)現(xiàn)成的數(shù)組進(jìn)行建立堆

基于這兩種方法我們提供了兩個(gè)構(gòu)造方法

堆排序的實(shí)現(xiàn)

我們直接把堆中的元素根據(jù)刪除原理進(jìn)行排序?就能實(shí)現(xiàn)把一個(gè)堆進(jìn)行排序了

就比如? 把最大的也就是堆頂?shù)脑?跟最小的元素交換 然后下潛，一直重復(fù)這個(gè)操作，直到最小的元素在數(shù)組的索引0位置即可

下面來(lái)看完整源碼

package heap.maxheap;import java.util.Arrays;public class MaxHeap {int[] array;//堆數(shù)組int size;//元素個(gè)數(shù)public MaxHeap(int capacity) {array = new int[capacity];}public MaxHeap(int[] arr) {array = arr;size = array.length;heap();}/*** 建堆方法*/private void heap() {//建堆 需要找到 葉子節(jié)點(diǎn)的父節(jié)點(diǎn)（最后一個(gè)元素）的索引位置 父節(jié)點(diǎn)//從父節(jié)點(diǎn) 開(kāi)始 依次進(jìn)行建堆操作//值得注意的是    我們建堆 找到的 是元素的索引位置// 是根據(jù) arr.length 也就是size 來(lái)進(jìn)行 尋找的//我們找到 葉子節(jié)點(diǎn)、父節(jié)點(diǎn)的索引位置 也就是下潛操作中 是根據(jù) 索引位置來(lái)尋找的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;//繼續(xù)上浮的條件應(yīng)該是  父節(jié)點(diǎn) 變成根節(jié)點(diǎn)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* 刪除堆頂?shù)脑? 刪除元素的時(shí)候 數(shù)組查找刪除比較慢 我們直接* 把數(shù)組尾部 跟 堆頂?shù)脑?交換刪除 然后下潛*/public int poll() {//此處應(yīng)有非空判斷我不想寫(xiě)了if(size==0){throw new IllegalArgumentException("元素為0 無(wú)法刪除");}int temp = array[0];swap(0, size - 1);size--;down(0);return temp;}/*** @param index 要?jiǎng)h除 指定元素的索引* @return int*/public int poll(int index) {if (index < 0 || index > size - 1) {throw  new IllegalArgumentException("索引位置錯(cuò)誤");}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;}//堆排序   怎么實(shí)現(xiàn)堆排序  我們只需要 拿到堆頂?shù)淖畲蟮脑?就行了public void heapSort(){while(size>1) {swap(0,size-1);size--;down(0);}System.out.println(Arrays.toString(array));}}

測(cè)試案例 如下

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();}
}

測(cè)試結(jié)果如下