Skip to main content

How to Sort Using Heap Sort in Python?

Here is how to sort using Heap Sort in Python?
Run the code here: https://repl.it/@VinitKhandelwal/heap-sort
def max_heapify(A, heap_size, i):
left = 2 * i + 1
right = left + 1
largest = i
if left < heap_size and A[left] > A[largest]:
largest = left
if right < heap_size and A[right] > A[largest]:
largest = right
if largest != i:
A[i], A[largest] = A[largest], A[i]
max_heapify(A, heap_size, largest)

def build_heap(A):
heap_size = len(A)
for i in range (int(heap_size/2),-1,-1):
max_heapify(A, heap_size, i)

def heapsort(A):
heap_size = len(A)
build_heap(A)
#print A #uncomment this print to see the heap it builds
for i in range(heap_size-1,0,-1):
A[0], A[i] = A[i], A[0]
heap_size -= 1
max_heapify(A, heap_size, 0)

A = [2,8,1,4,14,7,16,10,9,3]
heapsort(A)
print(A)

OUTPUT

[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

TIME COMPLEXITY

O(n log n)

Comments

Post a Comment

Popular posts from this blog

Python - List - Append, Count, Extend, Index, Insert, Pop, Remove, Reverse, Sort

🐍 Advance List List is widely used and it's functionalities are heavily useful. Append Adds one element at the end of the list. Syntax list1.append(value) Input l1 = [1, 2, 3] l1.append(4) l1 Output [1, 2, 3, 4] append can be used to add any datatype in a list. It can even add list inside list. Caution: Append does not return anything. It just appends the list. Count .count(value) counts the number of occurrences of an element in the list. Syntax list1.count(value) Input l1 = [1, 2, 3, 4, 3] l1.count(3) Output 2 It returns 0 if the value is not found in the list. Extend .count(value) counts the number of occurrences of an element in the list. Syntax list1.extend(list) Input l1 = [1, 2, 3] l1.extend([4, 5]) Output [1, 2, 3, 4, 5] If we use append, entire list will be added to the first list like one element. Extend, i nstead of considering a list as one element, it joins the two lists one after other. Append works in the following way. Input l1 = [1, 2, 3] l1.append([4, 5]) Output...
Post a Comment
Read more

Difference between .exec() and .execPopulate() in Mongoose?

Here I answer what is the difference between .exec() and .execPopulate() in Mongoose? .exec() is used with a query while .execPopulate() is used with a document Syntax for .exec() is as follows: Model.query() . populate ( 'field' ) . exec () // returns promise . then ( function ( document ) { console . log ( document ); }); Syntax for .execPopulate() is as follows: fetchedDocument . populate ( 'field' ) . execPopulate () // returns promise . then ( function ( document ) { console . log ( document ); }); When working with individual document use .execPopulate(), for model query use .exec(). Both returns a promise. One can do without .exec() or .execPopulate() but then has to pass a callback in populate.
1 comment
Read more

Resolve: Uncaught TypeError: firebase.database is not a function

If you are getting the error: Uncaught TypeError: firebase.database is not a function Resolve it by including firebase-database.js in your html page as follows: <!-- The core Firebase JS SDK is always required and must be listed first --> <script defer src = "https://www.gstatic.com/firebasejs/6.2.4/firebase-app.js" ></script> <script defer src = "https://www.gstatic.com/firebasejs/3.1.0/firebase-database.js" ></script> That is it. Let me know if this was helpful.
Post a Comment
Read more