Heapify the Vector

Slug: heapify-the-vector--102013

Difficulty: Basic

Id: 881705

Topic Tags: STL

Company Tags: None

Summary

The problem is to heapify a given vector, where heapifying means transforming the vector into a min-heap. This involves rearranging the elements of the vector such that each parent node is less than or equal to its children.

Detailed Explanation

To solve this problem, we can use the make_heap function from the <algorithm> library in C++. This function takes a random access iterator as input and heapifies the range [first, last).

Here's the step-by-step breakdown of the solution:

Include the necessary header files: <algorithm> and <vector>.
Use the make_heap function to heapify the vector.
The time complexity of this algorithm is O(n log n), where n is the size of the vector, because make_heap uses the Heapsort algorithm internally.
The space complexity is O(1) as we are not using any extra space.

Here's an example ASCII art diagram to illustrate the process:

     5
   /    \
 3       8
/ \    / \
2   4 6   9

In this diagram, the vector [5, 3, 8, 2, 4, 6, 9] is heapified to form a min-heap.

Optimized Solutions

Java

import java.util.Vector; import java.util.Arrays; public class Heapify { public static void main(String[] args) { Vector<Integer> vec = new Vector<>(); // Add elements to the vector Arrays.fill(vec, 1, 7, i -> (int)(Math.random() * 100)); make_heap(vec); System.out.println("Heapified vector: " + vec); } public static void make_heap(Vector<Integer> vec) { for (int i = vec.size() / 2 - 1; i >= 0; i--) { heapify(vec, i, vec.size() - 1); } } public static void heapify(Vector<Integer> vec, int i, int n) { int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l <= n && vec.get(l) > vec.get(largest)) largest = l; if (r <= n && vec.get(r) > vec.get(largest)) largest = r; if (largest != i) { int temp = vec.get(i); vec.set(i, vec.get(largest)); vec.set(largest, temp); heapify(vec, largest, n); } } }