1. Understanding Heaps using heapq in Python

Understanding heapq¶

• heapq in python is min-heap
• heapify rearranges the elements of array in-place

References:¶

1. https://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/

In [1]:

import heapq

import heapq

In [2]:

arr = [5, 7, 9, 1, 3]

arr = [5, 7, 9, 1, 3]

In [5]:

# heapify rearranges the elements of array in-place
heap = heapq.heapify(arr)

# heapify rearranges the elements of array in-place heap = heapq.heapify(arr)

In [6]:

arr

arr

Out[6]:

[1, 3, 9, 7, 5]

In [8]:

heapq.heappush(arr, 4)

heapq.heappush(arr, 4)

In [9]:

print(arr)

print(arr)

[1, 3, 4, 7, 5, 9]

In [11]:

heapq.heappop(arr)

heapq.heappop(arr)

Out[11]:

1

In [12]:

print(arr)

print(arr)

[3, 5, 4, 7, 9]

In [13]:

heapq.heappushpop(arr, 10)

heapq.heappushpop(arr, 10)

Out[13]:

3

In [14]:

print(arr)

print(arr)

[4, 5, 10, 7, 9]

In [15]:

heapq.heappushpop(arr, 3)

heapq.heappushpop(arr, 3)

Out[15]:

3

In [16]:

print(arr)

print(arr)

[4, 5, 10, 7, 9]

In [17]:

heapq.heapreplace(arr, 3)

heapq.heapreplace(arr, 3)

Out[17]:

4

In [18]:

print(arr)

print(arr)

[3, 5, 10, 7, 9]

In [19]:

heapq.nlargest(2, arr)

heapq.nlargest(2, arr)

Out[19]:

[10, 9]

In [20]:

heapq.nsmallest(2, arr)

heapq.nsmallest(2, arr)

Out[20]:

[3, 5]

In [ ]: