Home > Learning, Lesson, Problem, Projects/Experiments, Python > Python Sorting Algorithm – Heap Sorting -P3

Python Sorting Algorithm – Heap Sorting -P3


Learning : Python, Math, Algorithm
Subject: Sorting Algorithm, Heap Sort P2

[NOTE: To keep the code as simple as we can, We WILL NOT ADD any user input Varevecations. Assuming that our user will Enter the right inputs.]


First let’s just remember that in Part-1 we wort the Following Functions:

  • Main Menu Function.
  • Entering/Creating the Array.
  • Print-Out or to Display the Array.
  • Sections Header.

In this Part-3 we will cover another Two important Functions that we need to talk about in our mission to understand the Heap Sorting Algorithm.

First Function
Check If The Array is in Max Heap: After the user Giveing/Entering the Array [Selecting Option 1 in the Menu] we need to Examen/Check if it is in a Max-Heap, to do so we will call the Function def check_if_max_heap(arr, inside): the Function will take Two arguments:
arr : The Array.
inside: Boolean Flag showing are we calling the Function from within another Function or Not.

Scope of Work: We will check and compare each Node [starting from last node in the leaves] with it’s Parent using this formula parent_index = ((child_index-1)//2) to get the parent index, then comparing the Values of the Child and Parent, If the Child is GRATER Than his Parent we SWAP them. Then going to the Next Child and so-on until the Root-Node. .. Here is the Code ..

Ali radwani ahradwani.com python code heap sorting algorithm

for each print statement I am using this code if not inside : then print ..
Example: if not inside : print(‘\n The Array is a Max-Heap Array.’)
So if the inside = True then the print code will not work, that’s mean we are calling the Function from inside another function and we just want the return value, the return here will be a boolean True/False as is_max [if the array is in Max-Heap].

Second Function
Convert to Max-Heap: In this Function we will convert a given Array to a Max-Heap Array. The way this Function is working is by checking/Examining all the Childs starting from the Leaves, and if any Child is Grater than his Parent we do a SWAP. After we Finish, we will call the Function def check_if_max_heap(arr, inside): to check if the Array is in Max-Heap, If NOT we will call the convert Function and so-on until we get the is_max = True from the def check_if_max_heap(arr, inside):. Both Functions def check_if_max_heap(arr, inside): and def convert_to_max_heap (arr,inside): will be run in a while loop until def check_if_max_heap(arr, inside): will return True. .. Here is the code for def convert_to_max_heap (arr,inside):

Ali Radwani python code heap sorting algorithm


And here is the while loop to keep Examining the Array until fully converted to a Max-Heap Array.

 # While loop in Option 3 from the Main-Menu, In the main body code..

    while not is_max:
             arr = convert_to_max_heap (arr,True)
             is_max = check_if_max_heap (arr,True)
                



We will stop here in this part. In Part-4 we will Add new Node to the Array, and Delete a Node from the Array.

..:: Have Fun with Coding ::.. 🙂

To Download my Python code (.py) files Click-Here



ali radwani ahradwani.com python projects codeFollow me on Twitter..

By: Ali Radwani

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s