选择排序之堆排序(HeapSort)

谁借莪1个温暖的怀抱¢ 2021-06-10 20:41 548阅读 0赞

图解排序算法(三)之堆排序

一、堆定义

(二叉)堆是一个数组,类似于完全二叉树。分为两种形式:
这里写图片描述
这里写图片描述

二、维持堆性质

堆排序使用的是最大堆,如果堆中某个结点不满足最大堆性质,这时就需要用算法调整节点位置,使得满足最大堆性质。
这里写图片描述
这里写图片描述

三、建堆

默认数组为一个无序堆,通过数组前部分数组调用MAX-HEAPIFY函数来调整节点来使其满足最大堆性质。
这里写图片描述
这里写图片描述

四、堆排序

由于堆已经排好序,我们只需要逐渐取出节点就可以完成排序。堆排序对于记录数较少文件并不提倡。但对于n较大文件还是很有效。但是其运行时间主要消耗在建初始堆和调整新堆上。
这里写图片描述
这里写图片描述

1、建堆:从倒数第一个非叶子节点开始,逐个比较节点和其左右儿子节点的大小,如果将父节点和子节点交换,那么就需要再次验证交换后的子节点是否满足要求。
2、排序:从最后一个节点开始,逐个将节点和堆顶节点交换,这样就能把最大值一直拿出来。

  1. //实现
  2. public class Main{
  3. public static void main(String[] args){
  4. int[] a = {1,5,3,7,5,2,-1,6};
  5. heapSort(a);
  6. for(int i=0; i<a.length; i++)
  7. System.out.println(a[i]);
  8. }
  9. private static void heapSort(int[] a){
  10. buildHeap(a);
  11. for(int i=a.length-1; i>0; i--){ //从a.length-1到1逐渐交换,最优剩的0位置不用再排
  12. swap(a, i, 0);
  13. heapify(a, 0, i); //注意这个地方size一直在变化以避免再次将最大值加入堆中。
  14. }
  15. }
  16. private static void buildHeap(int[] a){
  17. int size = a.length;
  18. for(int i = (size-2)/2; i>=0; i--){ //从倒数第一个非叶子节点调整
  19. heapify(a, i, size);
  20. }
  21. }
  22. private static void heapify(int[] a, int i, int size){
  23. int left = 2*i+1;
  24. int right = 2*i+2;
  25. int largest = i;
  26. if(left<size && a[left]>a[largest]){
  27. largest = left;
  28. }
  29. if(right<size && a[right]>a[largest]){
  30. largest = right;
  31. }
  32. if(largest!=i){
  33. swap(a, largest, i);
  34. heapify(a, largest, size);
  35. }
  36. }
  37. private static void swap(int[] a, int i, int j){
  38. int temp = a[i];
  39. a[i] = a[j];
  40. a[j] = temp;
  41. }
  42. }

发表评论

表情:
评论列表 (有 0 条评论,548人围观)

还没有评论,来说两句吧...

相关阅读