堆的一個很重要的應用就是堆排序，和快速排序一樣，堆排序的時間復雜度也是O(NlgN)
堆排序的實現思路一：
1.創建小根堆
2.每次刪除頂部元素并將頂部元素輸出（刪除的函數中有調整的過程，每次調整）
時間復雜度：O(N·logN)

Input:
14
99 5 36 2 19 1 46 12 7 22 25 28 17 92

Output:
1 2 5 7 12 17 19 22 25 28 36 46 92 99

import java.util.Scanner; public class heap {static int n, num = 0;static int[] h = new int[15];static Scanner input = new Scanner(System.in);public static void main(String[] args) {n = input.nextInt();for (int i = 1; i <= n; i++) {h[i] = input.nextInt();}num = n;create();for (int i = 1; i <= n; i++) {System.out.print(deletemax() + " ");}}private static void create() {/*** 從最后一個非葉結點到第1個結點向上調整* */for (int i = num / 2; i >= 1; i--) {siftdown(i);}}private static int deletemax() {int temp = h[1];h[1] = h[num];num--;siftdown(1);return temp;}private static void siftup(int i) {int flag = 0;/*** 堆頂* */if (i == 1) {return;}while (i != 1 && flag == 0) {/*** 當前節點是否小于父結點* */if (h[i] < h[i/2]) {int temp = h[i];h[i] = h[i/2];h[i/2] = temp;} else {flag = 1;}/*** 向上調整* */i = i/2;}}private static void siftdown(int i) {int t, flag = 0;while (i * 2 <= num && flag == 0) {if (h[i] > h[i*2]) {t = i * 2;} else {t = i;}if (i * 2 + 1 <= num) {if (h[t] > h[i * 2 + 1]) {t = i * 2 + 1;}}if (t != i) {int temp = h[t];h[t] = h[i];h[i] = temp;i = t;} else {flag = 1;}}} }

---

堆排序的實現思路二：
1.創建大根堆
2.h[1]與h[n]交換
3.對h[1]向下調整, n–
時間復雜度：O(N·logN)

Input:
14
99 5 36 2 19 1 46 12 7 22 25 28 17 92

Output:
1 2 5 7 12 17 19 22 25 28 36 46 92 99

import java.util.Scanner; public class heapPlus {static int num, n = 0;static int[] h = new int[15];static Scanner input = new Scanner(System.in);public static void main(String[] args) {n = input.nextInt();for (int i = 1; i <= n; i++) {h[i] = input.nextInt();}num = n;create();heapsort();for (int i = 1; i <= n; i++) {System.out.print(h[i] + " ");}}private static void heapsort() {while (num > 1) {int temp = h[num];h[num] = h[1];h[1] = temp;num--;siftdown(1);}}private static void create() {/*** 從最后一個非葉結點到第1個結點向上調整* */for (int i = num / 2; i >= 1; i--) {siftdown(i);}}private static void siftup(int i) {int flag = 0;/*** 堆頂* */if (i == 1) {return;}while (i != 1 && flag == 0) {/*** 當前節點是否小于父結點* */if (h[i] > h[i/2]) {int temp = h[i];h[i] = h[i/2];h[i/2] = temp;} else {flag = 1;}/*** 向上調整* */i = i/2;}}private static void siftdown(int i) {int t, flag = 0;while (i * 2 <= num && flag == 0) {if (h[i] < h[i*2]) {t = i * 2;} else {t = i;}if (i * 2 + 1 <= num) {if (h[t] < h[i * 2 + 1]) {t = i * 2 + 1;}}if (t != i) {int temp = h[t];h[t] = h[i];h[i] = temp;i = t;} else {flag = 1;}}} }

堆是一種優先隊列的數據結構
對于普通隊列來說，在進行插入操作時比較方便，但是如果尋找隊列中最大（或最小）的元素則時間復雜度較高；
對于已排序的數組來說，查找最大（或最小）元素并不在話下，但是插入元素則需要后面的元素整體后移，時間復雜度依舊很高。
而優先隊列這種結構，則可以很好的解決上面的兩種操作。
之前的Dijkstra算法就可以通過堆來進行優化。

總結

以上是生活随笔為你收集整理的排序算法（二）--堆排序（JAVA）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。