What Is a Min Heap Data Structure?

//

Scott Campbell

A min heap is a binary tree-based data structure that maintains the minimum element at the root. It is often used in algorithms for efficient sorting, priority queue operations, and finding the kth smallest/largest element in a collection of elements. In this article, we will explore the concept of a min heap and understand how it works.

Heap Property

A min heap satisfies the heap property, which states that for every node n in the heap, the key (value) of n is smaller than or equal to the keys of its children. This property ensures that the minimum element is always at the root of the heap.

Binary Tree Representation

A min heap can be represented as a binary tree, where each node has at most two children. The tree is complete but not necessarily balanced. In a complete binary tree, all levels except possibly the last level are completely filled, and all nodes are as left as possible.

To visualize a min heap, imagine it as a binary tree with levels numbered from top to bottom and left to right. The topmost level (level 0) contains only one node (the root), level 1 contains two nodes, level 2 contains four nodes, and so on.

Example:

        5
      /   \
     8     10
    / \   /
   12 15 14

In this example, we have a min heap with five elements: [5, 8, 10, 12, 15]. The root node (5) is less than or equal to its children (8 and 10), which satisfies the heap property.

Array Representation

A min heap can also be represented using an array. The array representation allows for easy storage and retrieval of elements, as well as efficient implementation of heap operations.

In the array representation, the root of the min heap is stored at index 0. For any node at index i, its left child is located at index 2i + 1, and its right child is located at index 2i + 2.

Using the example above, the array representation would be: [5, 8, 10, 12, 15].

Operations on Min Heap

A min heap supports various operations:

  • Insertion: To insert a new element into a min heap, we add it to the next available position in the array representation and then perform a “heapify-up” operation to maintain the heap property.
  • Deletion (Extract Minimum): To extract the minimum element from a min heap (which is always at the root), we swap it with the last element in the array representation and then perform a “heapify-down” operation to restore the heap property.
  • Peek Minimum: To retrieve the minimum element from a min heap without removing it, we simply return the value at index 0.
  • Merge: Two min heaps can be merged by simply concatenating their array representations and then performing a “heapify-up” operation on each level to restore the heap property.

Time Complexity

The time complexity of common operations on a min heap are as follows:

  • Insertion: O(log n)
  • Deletion (Extract Minimum): O(log n)
  • Peek Minimum: O(1)
  • Merge: O(m + n), where m and n are the sizes of the two heaps being merged.

Conclusion

A min heap is a powerful data structure that allows for efficient sorting, priority queue operations, and finding the kth smallest/largest element. It maintains the minimum element at the root, satisfying the heap property. With its array representation and supported operations, a min heap provides an intuitive and performant solution to various algorithmic problems.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy