Heap Sort 讲解

30
十一月
2021

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.

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员