营销式网站,yw52777最新跳转接口,建设部网站 绿色建筑评价表,手机应用市场下载安装app堆的一个很重要的应用就是堆排序#xff0c;和快速排序一样#xff0c;堆排序的时间复杂度也是O(NlgN) 堆排序的实现思路一#xff1a; 1.创建小根堆 2.每次删除顶部元素并将顶部元素输出#xff08;删除的函数中有调整的过程#xff0c;每次调整#xff09; 时间复杂…堆的一个很重要的应用就是堆排序和快速排序一样堆排序的时间复杂度也是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算法就可以通过堆来进行优化。
