Heap

Heap

- nearly complete binary tree

- type: min heap, max heap

- uses: heapsort, priority queues

- height: logn

import heapq

A = [-4, 3, 1, 0, 2, 5, 10, 8, 12, 9]

heapq.heapify(A)
print(A)

heapq.heappush(A, 7)
print(A)

heapq.heappop(A)
print(A)

 

# Max Heap
B = [-4, 3, 1, 0, 2, 5, 10, 8, 12, 9]

for i in range(len(B)):
    B[i] = -B[i]

heapq.heapify(B)
print(B)

largest = -heapq.heappop(B)
print(largest)

 

min-heap

- value of i >= value of parent

- in order to make binary to min-heap, we need to heapify.

- heapify → T: O(n), S: O(1)

- heap pop: O(logn)

- heap push: O(logn)

 

Heap Sort

- Time complexity: O(n logn)

def heapsort(arr):
    heapq.heapify(arr)
    n = len(arr)
    new_list = [0] * n

    for i in range(n):
        minn = heapq.heappop(arr)
        new_list[i] = minn

    return new_list

print(heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]))