min heap python

1import heapq
2
3Since the built in heapq library is a minheap, multiply your values by -1
4and it will function as a max heap. Just remeber that all your numbers 
5have been inverted.

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

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