HEAP06 - Editorial

editorial
, ,
1

Problem Link - Implement complete heap

Problem Statement:

Complete the functions insert(), delete_from_heap() and heapify() to implement a min-heap in the code editor.

Approach:

The code focuses on basic heap operations: insertion, deletion, and reordering using Heapify. A min-heap ensures that the parent node is smaller than its child nodes.

void insert(int value):

This function inserts a new value by:

  1. Adding the value to the end of the internal array v.

  2. Reordering upwards: It compares the inserted element with its parent. If the parent is greater, they are swapped, and the process continues until the correct position is found.

void Heapify(int index):

This function restores the heap property after deletion by:

  1. Comparing the current node with its left and right children.

  2. Swapping the current node with the smallest child if necessary and recursively applying Heapify until the heap is properly ordered.

void delete_from_heap():

This function removes the root (smallest) element by:

  1. Swapping the root with the last element and removing the last element.

  2. Calling Heapify on the new root to maintain the heap structure.

Time Complexity:

  • Insert: O(log n) since we may need to traverse up to the root in the worst case.

  • Heapify: O(log n) as it may recursively adjust nodes down to the leaf level.

  • Delete: O(log n) because it calls Heapify after removing the root.

Space Complexity:

  • O(n) for storing n elements in the heap.