Heap Sort — [Introduction to Algorithms]
From now on, I’m going to start TIL on Introduction to Algorithms. We’ll look at why this book starts with sorting algorithms, and I’ll go through heap and heap sorting.
Why sorting algorithms?
Sorting is considered by many computer scientists to be the most fundamental topic in the algorithmic study. There are several reasons for this.
- There are some applications where sorting algorithms are required.
For example, The bank must sort the checks by check number in order to create a customer’s invoice.
2. Sorting is used in a lot of algorithms.
For example, A program that draws a layered object must arrange the data in a hierarchical order so that it can be drawn from bottom to top.
3. There are many different types of sorting algorithms, and many techniques are applied.
This book begins with sorting algorithms for these three reasons.
Heap
A heap data structure is an array object that can be viewed as a complete binary tree.
What is a complete binary tree?
Complete binary tree: A tree data structure with at most two child nodes for each node.
A node in this tree represents an element in the array.
As you can see in the figure above, the tree is full except for the last layer, and the last layer is filled in order from the left.
If the index of a node is given, the parent, left child, and right child of the node can be simply obtained with the following formula.
Parent = i/2
Left child = 2i
Right child = 2i + 1
Type of Heap
- Max Heap
In formula, we can represent Max Heap like this:
A[Parent(i)] ≥ A[i]
This means the parent node can not be smaller than the child node.
2. Min Heap
Also in the formula, we can represent like this:
A[Parent(i)] ≤ A[i]
This means the parent node can not be bigger than the child node.
Height of Heap
In view of the heap as a tree, the height of a node is defined as the number of edges of the longest down path from that node to a leaf. And the height of the heap is the height of the root.
Basic operation
- Max-Heapify
- It plays a key role in maintaining Max Heap characteristics.
- It runs in O(log n) time.
2. Build-Max-Heap
- It makes a max heap from an unordered array
- run in linear time.
3. Heapsort
- Sort the array internally.
- It runs in O(log n) time.
Preserving Heap Characteristics
To preserve the Max Heap characteristics, use Max-Heapify. Max-Heapify takes an array A and an index I as input.
Make Heap
To convert an unsorted array to the max heap, you must use Max-Heapify from the bottom up. The elements of subarray A[([n/2] + 1)..n] are all leaves of the tree. So you can create code like this:
Heap Sort
Finally, the title Heap Sort has appeared. But with a little thought, you’ll realize how easy it is to sort an array on max heap. (Hint: the root node of the max heap is the largest value in the array.)
To explain the code above, first, make the array the maximum heap. Following that, the array’s last and first values are swapped. After that, because the max heap characteristic may not be satisfied by the root node, it invokes Max Heapify to maintain the max heap characteristic. If the above procedure is repeated, the values will be moved to the back of the array in the order of largest value, resulting in a sorted array.
Conclusion
Today, I looked into a data structure called a heap, which I have always been curious about, and its characteristics, as well as how to sort an array through this structure. In the next article, we will learn about priority queues.
