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.

  1. 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.

Photo by Dmitry Demidko on Unsplash

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.

Photo by Minku Kang on Unsplash

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.

Complete binary tree

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

  1. 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.

Max Heap

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.

Height of Heap

Basic operation

  1. 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.

Example Image

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.

Buy me some coffee

--

--

--

Full Stack Dev

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Netlify Lambda Functions from Scratch

A community of 5,00,000 students!

The rise of the Biz Dev and gaining speed as well autonomy

reaching for the stars with power automate — credit: Mo, yes this is my doing

Introducing Endevor Team Build

CA Endevor Configurations for Source Code, Build and Ship

Top 5 Best Coding Challenge Websites

6 Helpful Writing Tips That Translate To Coding

What is GitHub Copilot?

How to securely access cloud resources from Linux VMs on Azure

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store

ki hyun Lee

Full Stack Dev

More from Medium

Recursion and stack

Salient points of Linked Lists in 3 mins

Rest API — What Is a Rest API?

Linked Lists — a Beginner’s Guide