Mastering Heaps: 5 Essential Algorithms for Optimal Performance

Immerse yourself in the world of heaps with this informative post. Explore five essential algorithms that leverage heaps to optimize performance and efficiency. Unlock the potential of heaps in your data structure and algorithms toolkit with this indispensable guide.

In this blog post, we will examine numerous heap algorithms and how they are used in software engineering and computer science. We will go over the key ideas and methods that each software engineer should be familiar with, from heap data structure to heap sort algorithm. Prepare yourself to enter the realm of heaps! You can run this post in Google Colab using this link:

1. Heap Data Structure

A heap is a tree-based data structure that satisfies the heap property. The heap property states that for every node $i$ other than the root, the value of the node is at least as large as the value of its parent. This is called a max-heap. A min-heap is defined similarly, except that each node is at least as small as its children. The root of the heap is the largest element in a max-heap and the smallest element in a min-heap. The heap property is listed below:

• A min-heap is a complete binary tree where each node is smaller than or equal to its children. This means that the root of the heap is the minimum element in the entire tree, and each subtree rooted at a node also satisfies the heap property.

• A max-heap is a complete binary tree where each node is greater than or equal to its children. This means that the root of the heap is the maximum element in the entire tree, and each subtree rooted at a node also satisfies the heap property.

Note: In both cases, the heap property ensures that the minimum or maximum element can be efficiently retrieved from the heap in O(1) time. Additionally, inserting and deleting elements in a heap while maintaining the heap property can be done in O(log n) time, where n is the number of elements in the heap.

Recap: A complete binary tree is a special type of binary tree in which every level of the tree is completely filled, except possibly for the last level. In the last level, all nodes are aligned as far left as possible. This means that a complete binary tree can be represented as an array, where the root is at index 0, its children are at indices 1 and 2, and so on. The parent of a node at index i is at index floor((i-1)/2). The children of a node at index i are at indices 2i+1 and 2i+2.

Recap: Binary trees are trees in which each node has at most two children. A binary tree is a full binary tree if each node has either zero or two children. A binary tree is a perfect binary tree if all interior nodes have two children and all leaves have the same depth or same level. A binary tree is a complete binary tree if all levels except possibly the last are completely filled and all nodes are as far left as possible.

1.1. Min Heap class

Wrtie a class called minHeap that implements a min-heap.

class minHeap:
    def __init__(self):
        self.heap = []
        self.size = 0

    def parent(self, i):
        return (i-1)//2

    def left(self, i):
        return 2*i + 1

    def right(self, i):
        return 2*i + 2

    def insertKey(self, k):
        self.size += 1
        i = self.size - 1
        self.heap.append(k)

        while i != 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def decreaseKey(self, i, new_val):
        self.heap[i] = new_val
        while i != 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def extractMin(self):
        if self.size <= 0:
            return float('inf')
        if self.size == 1:
            self.size -= 1
            return self.heap.pop()

        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.size -= 1
        self.minHeapify(0)

        return root

    def deleteKey(self, i):
        self.decreaseKey(i, float('-inf'))
        self.extractMin()

    def minHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        smallest = i

        if l < self.size and self.heap[l] < self.heap[i]:
            smallest = l
        if r < self.size and self.heap[r] < self.heap[smallest]:
            smallest = r
        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self.minHeapify(smallest)

    def getMin(self):
        return self.heap[0]

    def printHeap(self):
        print(self.heap)

Explanation:

• The Heap class has a constructor that takes in an array of integers and stores them in an instance variable called heap. The constructor also calls the build_heap method to build the heap from the array.

• The build_heap method builds a min-heap from the array of integers stored in the heap instance variable. It does this by calling the heapify method on each node in the tree, starting from the last node and working its way up to the root.

• The heapify method takes in an index i and recursively moves the node at index i down the tree until the heap property is satisfied. This is done by comparing the node at index i with its children. If the node at index i is greater than either of its children, then it is swapped with the smaller child. This process is repeated until the node at index i is smaller than both of its children.

• The insert method takes in an integer x and inserts it into the heap. It does this by appending x to the end of the array and then calling the heapify method on the last node in the tree.

• The extract_min method removes and returns the minimum element in the heap. It does this by swapping the root of the heap with the last node in the tree, removing the last node, and then calling the heapify method on the root of the tree.

• The get_min method returns the minimum element in the heap. It does this by returning the root of the tree.

• The size method returns the number of elements in the heap. It does this by returning the length of the array.

• The is_empty method returns True if the heap is empty and False otherwise. It does this by checking if the length of the array is equal to zero.

• The print_heap method prints the elements in the heap. It does this by iterating through the array and printing each element.

• The heap_sort method sorts the elements in the heap. It does this by repeatedly calling the extract_min method and appending the result to a list.

• The increase_key method takes in an index i and an integer x and increases the value of the node at index i by x. It does this by adding x to the node at index i and then calling the heapify method on the node at index i.

• The decrease_key method takes in an index i and an integer x and decreases the value of the node at index i by x. It does this by subtracting x from the node at index i and then calling the heapify method on the node at index i.

• The right and left methods return the indices of the right and left children of a node at index i, respectively. They do this by returning 2*i+2 and 2*i+1, respectively.

Time and Space Complexity:

• The build_heap method runs in O(n) time, where n is the number of elements in the heap. This is because it calls the heapify method on each node in the tree, starting from the last node and working its way up to the root. The build_heap method uses O(n) space, where n is the number of elements in the heap. This is because it creates an array of length n.

• The heapify method runs in O(log n) time, where n is the number of elements in the heap. This is because it compares the node at index i with its children and swaps it with the smaller child if necessary. This process is repeated until the node at index i is smaller than both of its children. The heapify method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The insert method runs in O(log n) time, where n is the number of elements in the heap. This is because it appends x to the end of the array and then calls the heapify method on the last node in the tree. The insert method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The extract_min method runs in O(log n) time, where n is the number of elements in the heap. This is because it swaps the root of the heap with the last node in the tree, removes the last node, and then calls the heapify method on the root of the tree. The extract_min method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The get_min method runs in O(1) time, where n is the number of elements in the heap. This is because it returns the root of the tree. The get_min method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The size method runs in O(1) time, where n is the number of elements in the heap. This is because it returns the length of the array. The size method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The is_empty method runs in O(1) time, where n is the number of elements in the heap. This is because it checks if the length of the array is equal to zero. The is_empty method runs in O(1) time, where n is the number of elements in the heap. This is because it checks if the length of the array is equal to zero.

• The print_heap method runs in O(n) time, where n is the number of elements in the heap. This is because it iterates through the array and prints each element. The print_heap method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The heap_sort method runs in O(n log n) time, where n is the number of elements in the heap. This is because it repeatedly calls the extract_min method and appends the result to a list. The heap_sort method uses O(n) space, where n is the number of elements in the heap. This is because it creates an array of length n.

• The increase_key method runs in O(log n) time, where n is the number of elements in the heap. This is because it adds x to the node at index i and then calls the heapify method on the node at index i. The increase_key method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The decrease_key method runs in O(log n) time, where n is the number of elements in the heap. This is because it subtracts x from the node at index i and then calls the heapify method on the node at index i. The decrease_key method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The right and left methods run in O(1) time, where n is the number of elements in the heap. This is because they return 2*i+2 and 2*i+1, respectively. The right and left methods use O(1) space, where n is the number of elements in the heap. This is because they do not create any new variables.

# example - insertKey, extractMin, decreaseKey, deleteKey

heap = minHeap()
print('heap = minHeap(): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(3)
print('heap.insertKey(3): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(2)
print('heap.insertKey(2): '), heap.printHeap()
print('-----------------------------------')

heap.deleteKey(1)
print('heap.deleteKey(1): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(15)
print('heap.insertKey(15): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(5)
print('heap.insertKey(5): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(4)
print('heap.insertKey(4): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(45)
print('Extract Minimum: ', heap.extractMin())
print('Heap after extract: '), heap.printHeap()
print('-----------------------------------')

print('New Minimum after extract min: ', heap.getMin())
heap.decreaseKey(2, 1)
print('heap.decreaseKey(2, 1): '), heap.printHeap()
print('New Minimum after decrease: ', heap.getMin())
print('-----------------------------------')

print('Final heap: '), heap.printHeap()

heap = minHeap():
[]
-----------------------------------
heap.insertKey(3):
[3]
-----------------------------------
heap.insertKey(2):
[2, 3]
-----------------------------------
heap.deleteKey(1):
[2]
-----------------------------------
heap.insertKey(15):
[2, 15]
-----------------------------------
heap.insertKey(5):
[2, 15, 5]
-----------------------------------
heap.insertKey(4):
[2, 4, 5, 15]
-----------------------------------
Extract Minimum:  2
Heap after extract:
[4, 15, 5, 45]
-----------------------------------
New Minimum after extract min:  4
heap.decreaseKey(2, 1):
[1, 15, 4, 45]
New Minimum after decrease:  1
-----------------------------------
Final heap:
[1, 15, 4, 45]





(None, None)

1.2. Max Heap class

class maxHeap:
    def __init__(self):
        self.heap = []
        self.size = 0

    def parent(self, i):
        return (i-1)//2

    def left(self, i):
        return 2*i + 1

    def right(self, i):
        return 2*i + 2

    def insertKey(self, k):
        self.size += 1
        i = self.size - 1
        self.heap.append(k)

        while i != 0 and self.heap[self.parent(i)] < self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def increaseKey(self, i, new_val):
        self.heap[i] = new_val
        while i != 0 and self.heap[self.parent(i)] < self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def extractMax(self):
        if self.size <= 0:
            return float('-inf')
        if self.size == 1:
            self.size -= 1
            return self.heap.pop()

        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.size -= 1
        self.maxHeapify(0)

        return root

    def deleteKey(self, i):
        self.increaseKey(i, float('inf'))
        self.extractMax()

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        largest = i

        if l < self.size and self.heap[l] > self.heap[i]:
            largest = l
        if r < self.size and self.heap[r] > self.heap[largest]:
            largest = r
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self.maxHeapify(largest)

    def getMax(self):
        return self.heap[0]

    def printHeap(self):
        print(self.heap)

Description:

• The MaxHeap class is a class that implements a max heap. It has the following methods:

  • build_heap: This method takes in an array and builds a max heap from the array. It does this by calling the heapify method on each node in the tree, starting from the last node and working its way up to the root.

  • heapify: This method takes in an index i and compares the node at index i with its children. If the node at index i is smaller than either of its children, it is swapped with the larger child. This process is repeated until the node at index i is larger than both of its children.

  • insert: This method takes in an integer x and inserts it into the heap. It does this by appending x to the end of the array and then calling the heapify method on the last node in the tree.

  • extract_max: This method removes and returns the maximum element in the heap. It does this by swapping the root of the heap with the last node in the tree, removing the last node, and then calling the heapify method on the root of the tree.

  • get_max: This method returns the maximum element in the heap. It does this by returning the root of the tree.

  • size: This method returns the number of elements in the heap. It does this by returning the length of the array.

  • is_empty: This method returns True if the heap is empty and False otherwise. It does this by checking if the length of the array is equal to zero.

  • print_heap: This method prints the elements in the heap. It does this by iterating through the array and printing each element.

  • heap_sort: This method sorts the elements in the heap. It does this by repeatedly calling the extract_max method and appending the result to a list.

  • increase_key: This method takes in an index i and an integer x and increases the value of the node at index i by x. It does this by adding x to the node at index i and then calling the heapify method on the node at index i.

  • decrease_key: This method takes in an index i and an integer x and decreases the value of the node at index i by x. It does this by subtracting x from the node at index i and then calling the heapify method on the node at index i.

  • right: This method takes in an index i and returns the index of the right child of the node at index i. It does this by returning 2*i+2.

  • left: This method takes in an index i and returns the index of the left child of the node at index i. It does this by returning 2*i+1.

Time Complexity and space Complexity:

• The build_heap method runs in O(n) time, where n is the number of elements in the heap. This is because it calls the heapify method on each node in the tree, starting from the last node and working its way up to the root. The build_heap method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The heapify method runs in O(log n) time, where n is the number of elements in the heap. This is because it compares the node at index i with its children and swaps it with the larger child if it is smaller than either of its children. This process is repeated until the node at index i is larger than both of its children. The heapify method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The insert method runs in O(log n) time, where n is the number of elements in the heap. This is because it appends x to the end of the array and then calls the heapify method on the last node in the tree. The insert method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The extract_max method runs in O(log n) time, where n is the number of elements in the heap. This is because it swaps the root of the heap with the last node in the tree, removes the last node, and then calls the heapify method on the root of the tree. The extract_max method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The get_max method runs in O(1) time, where n is the number of elements in the heap. This is because it returns the root of the tree. The get_max method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The size method runs in O(1) time, where n is the number of elements in the heap. This is because it returns the length of the array. The size method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The is_empty method runs in O(1) time, where n is the number of elements in the heap. This is because it checks if the length of the array is equal to zero. The is_empty method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The print_heap method runs in O(n) time, where n is the number of elements in the heap. This is because it iterates through the array and prints each element. The print_heap method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The heap_sort method runs in O(n log n) time, where n is the number of elements in the heap. This is because it repeatedly calls the extract_max method and appends the result to a list. The heap_sort method uses O(n) space, where n is the number of elements in the heap. This is because it creates a new list to store the sorted elements.

• The increase_key method runs in O(log n) time, where n is the number of elements in the heap. This is because it adds x to the node at index i and then calls the heapify method on the node at index i. The increase_key method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The decrease_key method runs in O(log n) time, where n is the number of elements in the heap. This is because it subtracts x from the node at index i and then calls the heapify method on the node at index i. The decrease_key method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The right method runs in O(1) time, where n is the number of elements in the heap. This is because it returns 2*i+2. The right method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

• The left method runs in O(1) time, where n is the number of elements in the heap. This is because it returns 2*i+1. The left method uses O(1) space, where n is the number of elements in the heap. This is because it does not create any new variables.

# example - insertKey, extractMax, increaseKey, deleteKey

heap = maxHeap()
print('heap = maxHeap(): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(3)
print('heap.insertKey(3): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(2)
print('heap.insertKey(2): '), heap.printHeap()
print('-----------------------------------')

heap.deleteKey(1)
print('heap.deleteKey(1): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(15)
print('heap.insertKey(15): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(5)
print('heap.insertKey(5): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(4)
print('heap.insertKey(4): '), heap.printHeap()
print('-----------------------------------')

heap.insertKey(45)
print('Extract Maximum: ', heap.extractMax())
print('Heap after extract: '), heap.printHeap()
print('-----------------------------------')

print('New Maximum after extract max: ', heap.getMax())
heap.increaseKey(2, 1)
print('heap.increaseKey(2, 1): '), heap.printHeap()
print('New Maximum after increase: ', heap.getMax())
print('-----------------------------------')

print('Final heap: '), heap.printHeap()

heap = maxHeap():
[]
-----------------------------------
heap.insertKey(3):
[3]
-----------------------------------
heap.insertKey(2):
[3, 2]
-----------------------------------
heap.deleteKey(1):
[3]
-----------------------------------
heap.insertKey(15):
[15, 3]
-----------------------------------
heap.insertKey(5):
[15, 3, 5]
-----------------------------------
heap.insertKey(4):
[15, 4, 5, 3]
-----------------------------------
Extract Maximum:  45
Heap after extract:
[15, 4, 5, 3]
-----------------------------------
New Maximum after extract max:  15
heap.increaseKey(2, 1):
[15, 4, 1, 3]
New Maximum after increase:  15
-----------------------------------
Final heap:
[15, 4, 1, 3]





(None, None)

2. Python build-in heapq module

In Python, heapq is a built-in module that provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. A heap is a special type of binary tree that satisfies the heap property, which specifies that the parent node is always greater than or equal to its children nodes (in a max heap) or less than or equal to its children nodes (in a min heap). The heap queue algorithm is useful for maintaining a collection of items with a priority, where the item with the highest priority is always at the front of the queue.

Here is an example of how to use heapq to implement a simple priority queue:

import heapq

# create an empty heap
heap = []

# add items to the heap with a priority
heapq.heappush(heap, (2, 'task 1'))
heapq.heappush(heap, (1, 'task 2'))
heapq.heappush(heap, (3, 'task 3'))

# get the item with the highest priority
highest_priority = heapq.heappop(heap)
print(highest_priority)  # output: (1, 'task 2')

(1, 'task 2')

In this example, we first create an empty heap. We then use the heappush() function to add items to the heap with a priority. Each item is a tuple containing the priority and the task description. The heappush() function automatically maintains the heap property by rearranging the items in the heap as necessary.

Finally, we use the heappop() function to get the item with the highest priority. The heappop() function removes the item from the heap and returns it as a tuple. In this case, the item with the highest priority is (‘task 2’, 1), which we print to the console.

Now let’s dive on some example of heap queue algorithm.

3. Continuous Median

Write a class to calculate continuous median that supports:

• The continuous insertation of numbers with the insert method
• the instant (O(1) time) retriival of the median of the numbers that have been inserted thus far with the getMedian method

Example:

insert(5)
insert(10)

getMedian() -> 7.5

import heapq

class ContinuousMedian:
    def __init__(self):
        self.max_heap = [] # to store the smaller half of numbers
        self.min_heap = [] # to store the larger half of numbers

    def insert(self, num):
        # If both heaps are empty, add to max heap
        if not self.max_heap and not self.min_heap:
            heapq.heappush(self.max_heap, -num)
            return

        # If num is smaller than max heap root, add to max heap
        if num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        # If num is larger than min heap root, add to min heap
        else:
            heapq.heappush(self.min_heap, num)

        # Balance the two heaps to ensure that the difference in size is at most 1
        if len(self.max_heap) - len(self.min_heap) > 1:
            num_to_move = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, num_to_move)
        elif len(self.min_heap) - len(self.max_heap) > 1:
            num_to_move = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -num_to_move)

    def getMedian(self):
        # If both heaps have the same size, take the average of the two roots
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2.0
        # Otherwise, return the root of the heap with the larger size
        elif len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        else:
            return self.min_heap[0]

Explanation:

The __init__ method initializes two empty lists: self.max_heap and self.min_heap. These will be used to keep track of the numbers that have been inserted so far.

The insert method takes a number and adds it to the appropriate heap. First, it checks if the number is less than or equal to the maximum value in the max heap. If it is, it adds the negative of the number to the max heap (so that the largest value is at the top). If the number is greater than the maximum value in the max heap, it adds it to the min heap.

The getMedian method returns the median of the numbers that have been inserted so far. If the number of elements in the max heap is greater than the number of elements in the min heap, it returns the maximum value in the max heap. If the number of elements in the min heap is greater than the number of elements in the max heap, it returns the minimum value in the min heap. If the number of elements in the max heap is equal to the number of elements in the min heap, it returns the average of the maximum value in the max heap and the minimum value in the min heap.

The ContinuousMedian class allows for the continuous insertion of numbers and the instant retrieval of the median. The code uses Python’s built-in heapq module to efficiently maintain the max heap and min heap, and takes advantage of the properties of heaps to make calculations faster.

Time and Space Complexity:

The time complexity of the insert method is O(log n) since inserting an element into a heap takes O(log n) time in the worst case, where n is the number of elements in the heap.

The time complexity of the getMedian method is O(1), since we are simply returning the median of the two heaps, which takes constant time.

The space complexity of the class is O(n), where n is the number of elements inserted into the heaps. This is because we are storing all the elements in the two heaps.

Testing:

# Create a new ContinuousMedian object
cm = ContinuousMedian()

# Insert some numbers
cm.insert(1)
cm.insert(2)
cm.insert(3)
cm.insert(4)

# Get the current median
print(cm.getMedian()) # Output: 2.5

# Insert some more numbers
cm.insert(5)
cm.insert(6)

# Get the updated median
print(cm.getMedian()) # Output: 3.5

2.5
3.5

4. Sort k-sorted array

Write a function that takes in a non-negetive integer k and a k-sorted array of integers and returns the sorted version of the array. Your function can either sort the array in place or create an entirely new array.

A k-sorted array is a partially sorted array in which all elements are at most k positions away from their sorted position. For example, the array [3, 1, 2, 2] is k-sorted with k = 2, because each element in the array is at most 2 positions away from its sorted position.

def sort_k_sorted_array(arr, k):
    n = len(arr)
    if n <= 1:
        return arr

    # Create a min-heap of size k+1
    heap = arr[:k+1]
    heapq.heapify(heap)

    # Add the smallest element from the heap to the sorted array,
    # and add the next element from the array to the heap
    sorted_arr = []
    for i in range(k+1, n):
        min_elem = heapq.heappop(heap)
        sorted_arr.append(min_elem)
        heapq.heappush(heap, arr[i])

    # Add the remaining elements in the heap to the sorted array
    while heap:
        min_elem = heapq.heappop(heap)
        sorted_arr.append(min_elem)

    return sorted_arr

Explanation:

The function takes in a k-sorted array and the value of k. The length of the array is stored in n. If the length of the array is less than or equal to 1, it means the array is already sorted and the function returns the array as is.

A new heap is created using the heapq module from Python’s standard library. The first k+1 elements of the array are used to create the heap, since the maximum displacement of an element from its final position in a k-sorted array is k. The heapify function is then used to turn the array into a heap.

A new list sorted_arr is created to store the sorted array. The loop iterates over the elements of the array starting from index k+1. In each iteration, the smallest element in the heap is popped using heappop, and appended to the sorted_arr. The next element from the array is then pushed onto the heap using heappush. This process continues until all elements of the array have been processed.

Finally, any remaining elements in the heap are popped using heappop and appended to the sorted_arr. The sorted_arr is returned as the sorted k-sorted array.

Time and Space Complexity:

The heapify operation takes O(k) time, and the push and pop operations take O(log(k)) time. The loop iterates over n-k elements, so it takes O((n-k)log(k)) time. The remaining elements in the heap are popped in O(klog(k)) time. The overall time complexity of the function is O(nlog(k)).

A heap of size k+1 is created, so the space complexity of the function is O(k). The additional space used for the sorted array is O(n-k), resulting in a total space complexity of O(n).

Testing:

# Test case 1
arr = [3, 1, 2, 2]
k = 2
expected_output = [1, 2, 2, 3]
assert sort_k_sorted_array(arr, k) == expected_output

# Test case 2
arr = [10, 9, 8, 7, 4, 70, 60, 50]
k = 4
expected_output = [4, 7, 8, 9, 10, 50, 60, 70]
assert sort_k_sorted_array(arr, k) == expected_output

# Test case 3
arr = [1, 2, 3, 4, 5]
k = 3
expected_output = [1, 2, 3, 4, 5]
assert sort_k_sorted_array(arr, k) == expected_output

# Test case 4
arr = [5, 4, 3, 2, 1]
k = 5
expected_output = [1, 2, 3, 4, 5]
assert sort_k_sorted_array(arr, k) == expected_output

# Test case 5
arr = [1]
k = 0
expected_output = [1]
assert sort_k_sorted_array(arr, k) == expected_output

# Test case 6
arr = []
k = 0
expected_output = []
assert sort_k_sorted_array(arr, k) == expected_output

5. Laptop rental

We are giving a list of time intervals during which students at a school need a laptop. These time intervals are represented by pairs of integers [start, end]. No two student can use a laptop at the same time, but immediatlety after studetns is done using laptop, another student can use that same laptop.

Wrtie a function that returns the minimum number of laptops that the school needs to rent such that all students will always have access to a laptop when they need one.

def min_laptops(intervals):
    times = []
    for start, end in intervals:
        times.append((start, 1))
        times.append((end, -1))
    times.sort()

    laptops_in_use = 0
    max_laptops = 0
    for time, delta in times:
        laptops_in_use += delta
        max_laptops = max(max_laptops, laptops_in_use)

    return max_laptops


def min_laptops_heap(intervals):
    # Sort the intervals based on their start times
    intervals.sort(key=lambda x: x[0])

    # Create a min-heap to keep track of the laptops that are currently available
    laptops = []

    # Iterate through the intervals and add or remove laptops from the heap as needed
    for interval in intervals:
        if laptops and laptops[0] <= interval[0]:
            # There is a laptop available for this interval, so remove it from the heap
            heapq.heappop(laptops)

        # Add a new laptop to the heap
        heapq.heappush(laptops, interval[1])

    # The size of the heap at the end will be the minimum number of laptops needed
    return len(laptops)

Explanation of code:

First method:

• We first create a list times that contains the start and end times of each interval. We also include a “delta” value of 1 for each start time and -1 for each end time. This will allow us to keep track of how many laptops are in use at any given time.
• We sort the times list in increasing order.
• We initialize two variables: laptops_in_use (the number of laptops currently in use) and max_laptops (the maximum number of laptops in use at any given time).
• We iterate through the times list. For each time interval, we update laptops_in_use by adding or subtracting the delta value. We also update max_laptops to be the maximum of the current value of max_laptops and laptops_in_use.
• Finally, we return max_laptops.

The time complexity of this method would be O(n log n) due to the sorting operation, where n is the number of time intervals. The space complexity would be O(n) to store the sorted intervals and the current laptop usage.

Heap method:

The algorithm first sorts the intervals based on their start times using the built-in sort method of Python lists, and then initializes an empty min-heap called laptops to keep track of the laptops that are currently available.

The algorithm then iterates through the intervals in the sorted order, and for each interval it checks if there is a laptop available for use. If there is a laptop available (i.e., if the end time of the laptop currently at the top of the heap is less than or equal to the start time of the current interval), the algorithm removes the laptop from the heap using the heappop method of the heapq module. It then adds the end time of the current interval to the heap using the heappush method.

At the end of the iteration, the size of the laptops heap represents the minimum number of laptops needed to schedule all the intervals, because the size of the heap corresponds to the maximum number of laptops that are needed simultaneously. This value is returned by the function.

The heap-based solution has a time complexity of O(n log k), where k is the number of available laptops. The space complexity would be O(k) to store the laptops in the heap. Therefore, the heap-based solution is more efficient for cases where the number of laptops is much smaller than the number of time intervals.

intervals1 = [(0, 30), (10, 20), (15, 25)]
print('First method: ', min_laptops(intervals1))  # Output: 3
print('Heap-based method: ', min_laptops_heap(intervals1))  # Output: 3

assert min_laptops_heap(intervals1) == 3
assert min_laptops(intervals1) == 3

intervals2 = [(0, 5), (2, 7), (4, 9), (6, 11)]
print('First method: ', min_laptops(intervals2))  # Output: 3
print('Heap-based method: ', min_laptops_heap(intervals2))  # Output: 3

assert min_laptops_heap(intervals2) == 3
assert min_laptops(intervals2) == 3

intervals3 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]
print('First method: ', min_laptops(intervals3))  # Output: 1
print('Heap-based method: ', min_laptops_heap(intervals3))  # Output: 1

assert min_laptops_heap(intervals3) == 1
assert min_laptops(intervals3) == 1

First method:  3
Heap-based method:  3
First method:  3
Heap-based method:  3
First method:  1
Heap-based method:  1