Heap Sort

09 Sep 2022 in Study / Computer science on Heap sorting

Algorithm

• a kind of sorting algorithm
• use the heap structure (max heap or min heap)

Property

• Always O(nlogn)
• Slower than other O(nlogn) sorting algorithms

Implementation 1

• In max heap, root node is maximum value
• Procedure
  • unsorted array → max heap (heapify)
  • root node ↔ end node
  • heapify again except end node (root node ~ (end - 1) node)
  • root node ↔ (end - 1) node
  • heapify again except (end - 1) node (root node ~ (end - 2) node)
  • repeat until sorting is completed
    

def heapSort(array):
    for i in range(1, len(array)):
        child = i

        while (child > 0):
            Parent = (child -1) // 2

            if array[child] > array[Parent]:
                array[child], array[Parent] = array[Parent], array[child]

            child = Parent

    for i in range(len(array) - 1, -1, -1):
        array[0], array[i] = array[i], array[0]
        movingNode = 0     # unsorted heap's root node

        while (movingNode * 2 + 1 < i):
            maxChild = movingNode * 2 + 1

            if movingNode * 2 + 2 < i and array[movingNode * 2 + 1] < array[movingNode * 2 + 2]:
                maxChild = movingNode * 2 + 2

            if array[movingNode] < array[maxChild]:
                array[movingNode], array[maxChild] = array[maxChild], array[movingNode]
            else:
                break

            movingNode = maxChild

• code Analysis
  

for i in range(1, len(array)):
    child = i

    while (child > 0):
        Parent = (child -1) // 2

        if array[child] > array[Parent]:
            array[child], array[Parent] = array[Parent], array[child]

        child = Parent

Code for array → max heap
i : 1 ~ end node index
i (start) → 0 : check the condition of max heap

---

for i in range(len(array) - 1, -1, -1):
    array[0], array[i] = array[i], array[0]
    movingNode = 0     # unsorted heap's root node

    while (movingNode * 2 + 1 < i):
        maxChild = movingNode * 2 + 1

        if movingNode * 2 + 2 < i and array[movingNode * 2 + 1] < array[movingNode * 2 + 2]:
            maxChild = movingNode * 2 + 2

        if array[movingNode] < array[maxChild]:
            array[movingNode], array[maxChild] = array[maxChild], array[movingNode]
        else:
            break

        movingNode = maxChild

swap between root node and end node
end node gradually reduces : len(array) - 1 → 0
As time goes by, two areas are formed (unsorted | sorted)
The node which was originally end node (len(array) - 1 → 0) before swapping will only move for reconstructing the max heap
2 * movingNode + 1 : movingNode’s left child node
2 * movingNode + 2 : movingNode’s right child node
compare between movingNode and max child node : if it is not satisfied with the condition of max heap, swapping happens

Implementation 2

• Use heapq
• min heap will be used for sorting based on ascending order
• max heap will be used for sorting based on descending order
• heapq.heappop() : automatically return min in current heap structure

import heapq

def minHeapSort(array):
  sortedResult = []
  minHeap = []

  for i in array:
    heapq.heappush(minHeap, i)

  for i in range(len(array)):
    sortedResult.append(heapq.heappop(minHeap))

  return sortedResult

import heapq

def maxHeapSort(array):
  sortedResult = []
  maxHeap = []

  for i in array:
    heapq.heappush(maxHeap, -i)

  for i in range(len(array)):
    sortedResult.append(-heapq.heappop(maxHeap))

  return sortedResult