[Sorting] Heap Sort 힙 정렬

Heap Sort is conceptually a kind of binary tree. The advantage of Heap Sort is that no extra memory is needed in the sorting process!

 

A heap must satisfy the heap property, which says that the priority of every node is greater than or equal to the priority of any child nodes of that node.

 

When a heap is used to implement a priority queue, each node contains one of the items in the queue along with the number that specifies the priority of that item.

 

A priority queue is a generalisation of the stack and the queue, which supports the operations of inserting a new element and deleting the largest element. Each element of the queue has a priority associated with it.

 

The basic idea of Heap Sort is simply to build a heap containing the elements to be sorted and then to remove them all in order.

 

# Pseudocode

buf: array
n: array size

largest: index of largest value
l: index of left node
r: index of right node

sort()
    n := buf.size()
    
    for i is (n / 2) - 1 to 0 do:
    	heapify(n, i)
    else for
    
    for i is (n - 1) to 1 do:
    	swap(0, i)
        heapify(i, 0)
    else for
end

heapify(n, i)
	if l < n and buf[l] > buf[largest]
    	largest := l
    if r < n and buf[r] > buf[largest]
    	largest := r
    if largest is not equal to i
    	swap(i, largest)
        heapify(n, largest)
end

 

# Computation in C

# Time Complexity

• Worst complexity: O(n*log(n))
• Average complexity: O(n*log(n))
• Best complexity: O(n*log(n))