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)
1#!/usr/bin/env python3
2# -*- coding: utf-8 -*-
3"""
4Created on Sun Mar 10 18:18:25 2019
5
6@source: https://www.geeksforgeeks.org/heap-sort/
7
8"""
9# Python program for implementation of heap Sort
10
11# To heapify subtree rooted at index i.
12# n is size of heap
13def heapify(arr, n, i):
14 largest = i # Initialize largest as root
15 l = 2 * i + 1 # left = 2*i + 1
16 r = 2 * i + 2 # right = 2*i + 2
17
18 # See if left child of root exists and is
19 # greater than root
20 if l < n and arr[i] < arr[l]:
21 largest = l
22
23 # See if right child of root exists and is
24 # greater than root
25 if r < n and arr[largest] < arr[r]:
26 largest = r
27
28 # Change root, if needed
29 if largest != i:
30 arr[i],arr[largest] = arr[largest],arr[i] # swap
31
32 # Heapify the root.
33 heapify(arr, n, largest)
34
35# The main function to sort an array of given size
36def heapSort(arr):
37 n = len(arr)
38
39 # Build a maxheap.
40 for i in range(n, -1, -1):
41 heapify(arr, n, i)
42
43 # One by one extract elements
44 for i in range(n-1, 0, -1):
45 arr[i], arr[0] = arr[0], arr[i] # swap
46 heapify(arr, i, 0)
47
48heapSort(arr)
49
50
1// @see https://www.youtube.com/watch?v=H5kAcmGOn4Q
2
3function heapify(list, size, index) {
4 let largest = index;
5 let left = index * 2 + 1;
6 let right = left + 1;
7 if (left < size && list[left] > list[largest]) {
8 largest = left;
9 }
10 if (right < size && list[right] > list[largest]) {
11 largest = right;
12 }
13 if (largest !== index) {
14 [list[index], list[largest]] = [list[largest], list[index]];
15 heapify(list, size, largest);
16 }
17 return list;
18}
19
20function heapsort(list) {
21 const size = list.length;
22 let index = ~~(size / 2 - 1);
23 let last = size - 1;
24 while (index >= 0) {
25 heapify(list, size, --index);
26 }
27 while (last >= 0) {
28 [list[0], list[last]] = [list[last], list[0]];
29 heapify(list, --last, 0);
30 }
31 return list;
32}
33
34heapsort([4, 7, 2, 6, 4, 1, 8, 3]);
1Implementation of heap sort in C:
2
3#include <stdio.h>
4int main()
5{
6 int heap[10], array_size, i, j, c, root, temporary;
7 printf("\n Enter size of array to be sorted :");
8 scanf("%d", &array_size);
9 printf("\n Enter the elements of array : ");
10 for (i = 0; i < array_size; i++)
11 scanf("%d", &heap[i]);
12 for (i = 1; i < array_size; i++)
13 {
14 c = i;
15 do
16 {
17 root = (c - 1) / 2;
18 if (heap[root] < heap[c]) /* to create MAX heap array */
19 { // if child is greater than parent swap them
20 temporary = heap[root]; // as structure is of complete binary tree
21 heap[root] = heap[c]; // it took logn steps to reach from root to leaf
22 heap[c] = temporary;
23 }
24 c = root;
25 } while (c != 0);
26 }
27 printf("Heap array : ");
28 for (i = 0; i < array_size; i++)
29 printf("%d\t ", heap[i]); //printing the heap array
30 for (j = array_size - 1; j >= 0; j--)
31 {
32 temporary = heap[0];
33 heap[0] = heap[j] ; /* swap max element with rightmost leaf element */
34 heap[j] = temporary;
35 root = 0;
36 do
37 {
38 c = 2 * root + 1; /* left node of root element */
39 if ((heap[c] < heap[c + 1]) && c < j-1)
40 c++;
41 if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */
42 {
43 temporary = heap[root];
44 heap[root] = heap[c];
45 heap[c] = temporary;
46 }
47 root = c;
48 } while (c < j);
49 }
50 printf("\n The sorted array is : ");
51 for (i = 0; i < array_size; i++)
52 printf("\t %d", heap[i]);
53}
1Heap Implementation at this link:
2
3https://github.com/shreyasvedpathak/Data-Structure-Python/tree/master/Hashing