Heap Sort Algorithm: Explanation and Code

In this guide, we’ll take a deep dive into the heap data structure, exploring its various types, applications, and how it operates through real-world examples and code snippets. By the time we’re done, you’ll have a solid understanding of heaps and know exactly when to put them to use.

If you’re looking to get hands-on experience and master complex data structures with guidance from experts, check out the [Data Structures Course in Noida (uncodemy.com)].

What Is a Heap?

• 

  Mr. Rajesh Kumar Mandal / 15 days
• 11
• 17 min read

A heap is a unique data structure based on a binary tree that adheres to the heap property. It’s a complete binary tree, which means that all levels are filled except possibly the last one, and that last level is filled from left to right.

The heap property varies depending on the type:

- Max-Heap: In this case, parent nodes are greater than or equal to their children.

- Min-Heap: Here, parent nodes are less than or equal to their children.

This design allows heaps to efficiently manage priority queues, ensuring that the highest (or lowest) priority element is always accessible in constant time.

Characteristics of Heap

Here are some key features that define a heap:

- Complete Binary Tree: This ensures efficient memory usage and a predictable structure.

- Heap Order Property: The key at the root must be the maximum (in a max-heap) or the minimum (in a min-heap).

- Efficient Access to Root: The top element (whether maximum or minimum) is always at the root and can be accessed in O(1) time.

- Efficient Insertion and Deletion: Adding or removing elements in a heap takes O(log n) time because we need to maintain the heap property.

Different types of heaps

1. Max-Heap

In a max-heap, every parent node holds a value that's greater than or equal to its children's values. This means the largest element is always found at the root.

Example:

        90
   	/  \
 	15	10
	/  \
   7	12

2. Min-Heap

On the flip side, a min-heap has parent nodes with values that are less than or equal to those of their children. So, the smallest element is located right at the root.

Example:

	5
   	/ \
 	10   15
	/  \
  20   30

Heap Representation in Memory

Heaps are usually represented as arrays. For any node located at index i:

Left child: 2 * i + 1

Right child: 2 * i + 2

Parent: (i - 1) / 2

This array-based approach not only makes heaps memory-efficient but also easy to work with!

Heap Operations

1. Insertion in Heap

When you add a new element:

Start by placing it at the end of the array (the last leaf).

Then, use "Heapify Up" or "Bubble Up" to adjust the element and keep the heap property intact.

Time Complexity: O(log n)

2. Deletion in Heap

Typically, deleting an element means removing the root (which is either the maximum or minimum):

To do this, swap the root with the last element.

Next, perform "Heapify Down" to restore the heap property.

Time Complexity: O(log n)

3. Heapify

Heapify is the process of transforming a binary tree into a valid heap. You can approach this in either a bottom-up or top-down fashion.

Time Complexity:

- Building a heap: O(n)

- Heapify: O(log n)

C++ Code: Max Heap Insertion Example

#include 
#include 
using namespace std;
 
void heapify(vector& heap, int i) {
	int size = heap.size();
	int largest = i;
	int left = 2*i + 1;
	int right = 2*i + 2;
 
	if (left < size && heap[left] > heap[largest])
    	largest = left;
	if (right < size && heap[right] > heap[largest])
    	largest = right;
 
	if (largest != i) {
        swap(heap[i], heap[largest]);
        heapify(heap, largest);
	}
}
 
void insert(vector& heap, int val) {
    heap.push_back(val);
	int i = heap.size() - 1;
	while (i > 0 && heap[(i-1)/2] < heap[i]) {
        swap(heap[i], heap[(i-1)/2]);
    	i = (i-1)/2;
	}
}
 
void displayHeap(const vector& heap) {
	for (int val : heap) cout << val << " ";
	cout << endl;
}
 
int main() {
    vector heap;
	insert(heap, 10);
	insert(heap, 20);
	insert(heap, 5);
	insert(heap, 30);
 
    displayHeap(heap);
	return 0;
}

Applications of Heap

1. Priority Queues

Heaps play a crucial role in implementing priority queues, ensuring that elements with higher priorities are processed before those with lower ones.

2. Heap Sort

Heap is a key component in heap sort, a highly efficient in-place sorting algorithm that operates with a time complexity of O(n log n).

3. Graph Algorithms

Heaps are utilized in Dijkstra’s and Prim’s algorithms, which are essential for finding the shortest path and constructing minimum spanning trees, respectively.

4. Median Maintenance

Both min and max heaps are employed in data stream processing to calculate the median in real-time.

5. Scheduling Algorithms

Operating systems rely on heap-based structures to manage process scheduling according to priority.

Heap vs Binary Search Tree (BST)

Heap Sort Algorithm

Heap Sort is a sorting method that relies on a heap data structure and is based on comparisons. It operates in two main steps:

First, it builds a max heap from the input data.

Then, it swaps the root (which is the maximum value) with the last element and reduces the size of the heap. After that, it heapifies the root again.

Time Complexity:

Worst: O(n log n)

Best: O(n log n)

Space: O(1)

Real-Time Event Handling with Heaps

In today’s fast-paced computing world, especially when it comes to real-time operations, it’s essential to handle events quickly and accurately. That’s where a heap data structure shines as a perfect foundation for real-time event management systems, thanks to its knack for prioritizing tasks based on urgency or timing.

Picture a real-time simulator juggling multiple events set to happen at different intervals—think animations in a game engine, sensor data in embedded systems, or packet transfers in networking. These events need to be executed not in the order they were added, but according to their deadlines or priority levels.

This is where a min-heap really comes into play. By organizing events in a min-heap, the system can swiftly access the event with the earliest deadline, conveniently located at the root of the heap. As new events come in or old ones are removed, the heap automatically rearranges itself to keep the next most urgent task ready for action. This leads to optimal CPU usage and timely responses, which are vital in areas like robotics, avionics, and healthcare.

For example, in a multimedia streaming server, heaps can help determine which data packets should be sent first based on their playback priority. Likewise, in operating systems, real-time schedulers can leverage heaps to ensure that high-priority threads are executed before others.

In summary, heaps provide a dependable and efficient way to manage time-sensitive operations, making them essential in the realm of real-time computing.

Advantages of Heap

- Quick access to the highest or lowest priority element

- Efficient for implementing priority queues

- Delivers strong performance in sorting tasks

- Utilizes a straightforward array-based structure

Disadvantages of Heap

- Not ideal for quickly searching arbitrary elements

- Less flexible compared to balanced binary search trees (like AVL or Red-Black Trees)

- Re-heapifying can take time for complex updates

When to Use a Heap?

Consider using a heap when:

- You need to frequently access the highest or lowest element.

- You're working on a scheduler, priority queue, or a real-time algorithm.

- You require sorting with O(n log n) performance while keeping space usage minimal.

Conclusion

The heap data structure plays a crucial role in many sophisticated algorithms and real-world applications. Thanks to its array-based design and reliable performance, it’s perfect for scenarios that need quick access to extreme values.

Whether you’re developing schedulers, implementing Dijkstra’s algorithm, or crafting custom sorting methods, heaps are absolutely essential.

If you’re eager to grasp heaps in a practical way and lay a strong foundation in data structures, consider enrolling in the [Data Structures Course in Noida (uncodemy.com)]. This course dives into heaps, trees, queues, graphs, and more, featuring hands-on projects, real-time problem-solving, and expert guidance.

Frequently Asked Questions (FAQs)

Q1. What is a heap in data structure?

A heap is a complete binary tree that adheres to the heap property, meaning parent nodes are either greater or smaller than their child nodes, depending on whether it’s a max heap or a min heap.

Q2. What is the difference between heap and stack?

The heap is used for dynamic memory allocation and follows specific ordering rules, while the stack is a linear data structure that operates on a LIFO (Last In First Out) basis.

Q3. What is heapify?

Heapify is the process of transforming a binary tree into a heap by rearranging its elements to uphold the heap property.

Q4. What is the time complexity of insertion and deletion in a heap?

Both insertion and deletion operations in a heap take O(log n) time because of the need to maintain the heap structure.

Q5. Where are heaps used in real life?

Heaps are commonly found in priority queues, scheduling algorithms, Dijkstra’s algorithm, real-time systems, and heap sort.

Q6. Which data structure is used in priority queues?

Heaps, particularly binary heaps, are the go-to data structures for implementing priority queues.

Q7. What are the advantages of heap sort?

Heap sort boasts O(n log n) performance and doesn’t require extra memory (it’s in-place). It’s also more reliable than quicksort in the worst-case scenario.