Heap

"""
A heap is a specialized tree-based data structure that satisfies the heap property. In a heap, for any given node C, if P is a parent node of C, then the key (the value) of node P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of node C. The node at the "top" of the heap (with no parents) is called the root node.

Types of Heaps
- Max Heap: In a max heap, for any given node C and parent node P, the key of P is greater than or equal to the key of C. Thus, the node with the greatest key is always the root node of the tree.
- Min Heap: In a min heap, for any given node C and parent node P, the key of P is less than or equal to the key of C. Thus, the node with the smallest key is always the root node of the tree.

In Python, the heapq module provides an implementation of the min heap. By default, heapq creates a min heap, where the smallest element is always popped first. Here's a quick overview of some of the functions provided by the heapq module:

- heapq.heappush(heap, item): Pushes a new item onto the heap, maintaining the heap invariant.
- heapq.heappop(heap): Pops and returns the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised.
- heapq.heapify(x): Transforms the list x into a heap in linear time.
"""

import heapq

def heap(nums, k):
    # Initialize a min heap
    min_heap = nums[:k]
    heapq.heapify(min_heap)

    # Iterate through the rest of nums
    for num in nums[k:]:
        if num > min_heap[0]:  # If current num is larger than the smallest in heap
            heapq.heappop(min_heap)  # Remove the smallest
            heapq.heappush(min_heap, num)  # Push the current num

    # The heap contains the k largest elements
    return min_heap

# Example usage
nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]
k = 4
print(heap(nums, k))
# Output: [4, 5, 5, 6]