你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

Heap Sort 讲解

2021-11-30 3:20:43

Heap Sort sorts a group of unordered elements using the Heap data structure.

The sorting algorithm using a Min Heap is as follows:

  1. Heapify all elements into a Min Heap
  2. Record and delete the top element
  3. Put to top element into an array T that stores all sorted elements. Now, the Heap will remain a Min Heap
  4. Repeat steps 2 and 3 until the Heap is empty. The array T will contain all elements sorted in ascending order.

The sorting algorithm using a Max Heap is as follows:

  1. Heapify all elements into a Max Heap
  2. Record and delete the top element
  3. Put the top element into an array T that stores all sorted elements. Now, the Heap will remain a Max Heap
  4. Repeat steps 2 and 3 until the Heap is empty. The array T will contain all elements sorted in descending order.

Complexity Analysis:
Let N be the total number of elements.
Time complexity: O(N log N)
Space complexity: O(N)


Using a heap to obtain a sorted array involves converting the unsorted array into a heap, then popping the elements from the heap one at a time and adding them to the new sorted array.