Java learning heap sorting process diagram and code explanation

This article mainly explains the heap sorting process in the form of pictures, and then uses Java code to implement heap sorting and analyze the time complexity. It has certain reference value and interested friends can learn more.

1. Introduction2. Illustrated heapsort 3. Java code implementation and time complexity analysis 4. Summary

## 1. Introduction

Priority queue can be used to sort in O(NlogN) time, just like the idea used in solving the topK problem in the previous article, this idea is heap sort (heapsort).

2. Graphical heap sort (heapsort)

1. Algorithm idea: Heap sort by buildingHeap the array elements (build a large top heap); then perform N-1 deleteMax operations on the heap. Here is a trick. If you use a new array to store, it will require O(N) space; but each time deleteMax will vacate a position and filter down the tail nodes, then we can deleteMax The data is placed at the end.
2. Heap sorting process:

If you don’t know about the binary heap, you can take a look at the graphic priority queue (heap)

3. Java code implementation and time complexity analysis

We start from the array It starts at index 0, unlike the binary heap which starts at array index 1.

• Code implementation

• public class Heapsort {
      public static void main(String[] args) {
          Integer[] integers = {7, 1, 13, 9, 11, 5, 8};
          System.out.println("原序列：" + Arrays.toString(integers));
          heapsort(integers);
          System.out.println("排序后：" + Arrays.toString(integers));
      }
  
      public static <T extends Comparable<? super T>> void heapsort(T[] a) {
          if (null == a || a.length == 0) {
              throw new RuntimeException("数组为null或长度为0");
          }
          //构建堆
          for (int i = a.length / 2 - 1; i >= 0; i--) {
              percDown(a, i, a.length);
          }
          //deleteMax
          for (int i = a.length - 1; i > 0; i--) {
              swapReferences(a, 0, i);
              percDown(a, 0, i);
          }
      }
  
      /**
       * 下滤的方法
       *
       * @param a：待排序数组
       * @param i：从哪个索引开始下滤
       * @param n           ：二叉堆的逻辑大小
       * @param <T>
       */
      private static <T extends Comparable<? super T>> void percDown(T[] a, int i, int n) {
          int child;
          T tmp;
          for (tmp = a[i]; leftChild(i) < n; i = child) {
              child = leftChild(i);
              if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0) {
                  child++;
              }
              if (tmp.compareTo(a[child]) < 0) {
                  a[i] = a[child];
              } else {
                  break;
              }
          }
          a[i] = tmp;
      }
  
      private static int leftChild(int i) {
          return 2 * i + 1;
      }
  
      /**
       * 交换数组中两个位置的元素
       *
       * @param a：目标数组
       * @param index1 ：第一个元素下标
       * @param index2 ：第二个元素下标
       * @param <T>
       */
      private static <T> void swapReferences(T[] a, int index1, int index2) {
          T tmp = a[index1];
          a[index1] = a[index2];
          a[index2] = tmp;
      }
  }
  //输出结果
  //原序列：[7, 1, 13, 9, 11, 5, 8]
  //排序后：[1, 5, 7, 8, 9, 11, 13]

• Time complexity: buildHeap Using O(N) time, filtering down elements requires O(logN), and filtering down N-1 times is required, so a total of O(N (N-1)logN) = O(NlogN) is required. It can be seen from the process that the heap sorting, no matter the best or worst time complexity, is stable at O(NlogN).

• Space complexity: Using its own storage is undoubtedly O(1).

##4. Summary

This article illustrates the process of heap sorting through drawing, making it clear and clear

Heap sort is first heap-sorted and then sorted by deleteMax. Its space complexity is O(1), and its time complexity is stable at O(NlogN).

The above is the detailed content of Java learning heap sorting process diagram and code explanation. For more information, please follow other related articles on the PHP Chinese website!