heap in python

1>>> import heapq
2>>> heap = []
3>>> heapq.heappush(heap, (5, 'write code'))
4>>> heapq.heappush(heap, (7, 'release product'))
5>>> heapq.heappush(heap, (1, 'write spec'))
6>>> heapq.heappush(heap, (3, 'create tests'))
7>>> heapq.heappop(heap)#pops smallest
8(1, 'write spec')
9>>> heapq.nlargest(2,heap)#displays n largest values without popping
10[(7, 'release product'),(5, 'write code')]
11>>> heapq.nsmallest(2,heap)#displays n smallest values without popping
12[(3, 'create tests'),(5, 'write code')]
13>>> heap = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
14>>> heapq.heapify(heap)#converts a list to heap
15>>> heap
16[0, 1, 2, 6, 3, 5, 4, 7, 8, 9]
17>>> def heapsort(iterable):
18...     h = []
19...     for value in iterable:
20...         heappush(h, value)
21...     return [heappop(h) for i in range(len(h))]
22...
23>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
24[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
25

1def buildHeap(lista, n):
2    for i in range(n//2 - 1, -1, -1):
3        heapify(lista, n, i)
4
5def heapify(lista, n, i):
6    largest = i  
7    left = (2 * i) + 1    
8    right = (2 * i) + 2 
9
10    if left < n and lista[largest] < lista[left]:
11        largest = left
12
13    if right < n and lista[largest] < lista[right]:
14        largest = right
15
16    if largest != i:
17        lista[i], lista[largest] = lista[largest], lista[i] 
18        heapify(lista, n, largest) 
19
20def heapSort(lista):
21    n = len(lista)
22    buildHeap(lista, n)
23    
24    for i in range(n-1, 0, -1):
25        lista[i], lista[0] = lista[0], lista[i]
26        heapify(lista, i, 0)

1#Implementing Heap Using Heapify Method in Python 3
2#MaxHeapify,MinHeapify,Ascending_Heapsort,Descending_Heapsort
3class heap:
4    
5    def maxheapify(self,array):
6        n=len(array)
7        for i in range(n//2-1,-1,-1):
8            self._maxheapify(array,n,i)
9            
10            
11    def _maxheapify(self,array,n,i):
12        l=2*i+1
13        r=2*i+2
14        if l<n and array[l]>array[i]:
15            largest=l
16        else:
17            largest=i
18        if r<n and array[r]>array[largest]:
19            largest=r
20        if (largest!=i):
21            array[largest],array[i]=array[i],array[largest]
22            self._maxheapify(array,n,largest)
23            
24            
25    def minheapify(self,array):
26        n = len(array)
27        for i in range(n//2-1,-1,-1):
28            self._minheapify(array,n,i)
29            
30            
31    def _minheapify(self,array,n,i):
32        l=2*i+1
33        r=2*i+2
34        if l<n and array[l]<array[i]:
35            smallest = l
36        else:
37            smallest = i
38        if r < n and array[r]<array[smallest]:
39            smallest = r
40        if (smallest != i):
41            array[smallest], array[i] = array[i], array[smallest]
42            self._minheapify(array, n, smallest)
43            
44            
45    def descending_heapsort(self,array):
46        n = len(array)
47        for i in range(n // 2 - 1, -1, -1):
48            self._minheapify(array, n, i)
49        for i in range(n - 1, 0, -1):
50            array[0], array[i] = array[i], array[0]
51            self._minheapify(array, i, 0)
52
53
54    def ascending_heapsort(self,array):
55        n=len(array)
56        for i in range(n//2-1,-1,-1):
57            self._maxheapify(array,n,i)
58        for i in range(n-1,0,-1):
59            array[0],array[i]=array[i],array[0]
60            self._maxheapify(array,i,0)
61
62b=[550,4520,3,2340,12]
63a=heap()
64
65a.maxheapify(b)
66print('Max Heapify -->',b)
67
68a.minheapify(b)
69print('Min Heapify -->',b)
70
71a.ascending_heapsort(b)
72print('Ascending Heap Sort -->',b)
73
74a.descending_heapsort(b)
75print('Descending Heap Sort -->',b)

1def min_heapify(A,k):
2    l = left(k)
3    r = right(k)
4    if l < len(A) and A[l] < A[k]:
5        smallest = l
6    else:
7        smallest = k
8    if r < len(A) and A[r] < A[smallest]:
9        smallest = r
10    if smallest != k:
11        A[k], A[smallest] = A[smallest], A[k]
12        min_heapify(A, smallest)
13
14def left(k):
15    return 2 * k + 1
16
17def right(k):
18    return 2 * k + 2
19
20def build_min_heap(A):
21    n = int((len(A)//2)-1)
22    for k in range(n, -1, -1):
23        min_heapify(A,k)
24
25A = [3,9,2,1,4,5]
26build_min_heap(A)
27print(A)
28

1Heap Implementation at this link:
2
3https://github.com/shreyasvedpathak/Data-Structure-Python/tree/master/Hashing