Archive

Posts Tagged ‘Heap sorting’

Python Sorting Algorithm – Heap Sorting -P5


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

[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.]


In Last Parts (2, 3 and 4) we wort the Following Functions:

  • Sections Header.
  • Main Menu Function.
  • Entering/Creating the Array.
  • Print-Out or to Display the Array.
  • Check If Array in Max-Heap.
  • Convert Array to Max-Heap.
  • Add Node to Max-Heap.
  • Delete a Node from a Max-Heap.

In this last part-5 we will write the last main Function to aplay the Heap Sorting Algorithm.

Scope of Work: Deleting a Node from a Max-Heap Array is the main function in sorting an Array using Max-Heap Algorithm, the Deleting is always from the Root Node, So if we delete the most top Node [Root] (and store it in index[0] in a temp_array) then we move the Last Node to it’s position and by doing that we miss the Max-Heap state of the Array, so we convert the array to a Max-heap, then we Delete the Root again until we delete all the elements in the Array.. Here the Algorithm:

Assuming we have a Max-Heap Array:
1. Delete the Root Element, and Store it in index[0] in Temp_array.
2. Move the Last Element in the Array to index[0].
3. If the Array not in Max-Heap then Convert it to a Max-Heap.
4. Repeat Steps 1 to 3 Until length of Array is 0.

In our list of Functions up, we have the three Functions we Need to complete/apply a Max-Heap Sorting:
We Delete a Node using def delete_node(arr,inside):
then in a while loop we call both
def check_if_max_heap (arr,inside): and
def convert_to_max_heap (arr,inside): so let’s see the code..

ali radwani ahradwani.com python project code heap sorting algorithm


We finish Max-Heap Sorting Algorithm, ..

..:: 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

Python Sorting Algorithm – Heap Sorting -P4


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.]


In Last Parts (2 & 3) we wort the Following Functions:

  • Sections Header.
  • Main Menu Function.
  • Entering/Creating the Array.
  • Print-Out or to Display the Array.
  • Check If Array in Max-Heap.
  • Convert Array to Max-Heap.

In this Part-4 we will cover another Two important Functions that we need to talk about in our mission to understand the Heap Sorting Algorithm. In a Max-Heap Array we may need to Add new Node to the Array and we may need to Delete a Node. Also I just add Item No.7 style=”color:#2662ee;”>print(‘ ‘*5,’ 7. Start Heap Sorting.’) to the main-menu so we can do Heap Sorting to a given Array.

Starting with Add New Node, Simply we Add the Node to the end of the Array using arrat.append(new_node) then we need to Check If still the Array in Max-Heap If NOT, We MUST Convert it to a Max-Heap.

Scope of Work Ask the user to Enter the New Node Value, Add The Node to the End of the Array, in While Loop Call convert_to_max_heap (arr,True), check_if_max_heap (arr,True) as following:
while not is_max:
arr = convert_to_max_heap (arr,True)
is_max = check_if_max_heap (arr,True)
this will keep check and convert the Array to Max-Heap. Here is the Full code and run screen ..

ali radwani ahradwani.com python project code heap sorting
ali radwani ahradwani.com python project code math algorithm doha qatar



Now we will write a Function to Delete a Node from the Max-Heap Array. Deleting a Node is just by removing the first node in the Array (Array[0]), then moving the last element in the Array to it’s position, by doing this we may not having a Max-Heap Array any-more, so we need to convert the array to a Max-Heap. In our application here, we will have a while loop and calling the functions (check_if_max_heap and convert_to_max_heap) until we have the Array in a Max-Heap. Here is the code ..


We will stop here in this part. In Part-5 we will Sort any Array using the Max-Heap Sort Algorithm.

..:: 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

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

Python Sorting Algorithm – Heap Sorting -P2


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.]

In this post we will start writing some codes for the Heap Sorting application, we will start with the following Functions:

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


So First: We will start with the Main_menu Function and will return user_choice also the main application body.. Here is the code ..

 # Main Menu function and the main application body..

    
def main_menu():
    os.system('clear')
    header()
    print("\n\n"," "*4,"==============[ Main Menu ]==============\n")
    print(' '*5,' 1. Enter the Binary Tree as an Array.')
    print(' '*5,' 2. Print out the Binary Tree. {Text Mode}')
    print(' '*5,' 3. Check if it is a Max Heap.')
    print(' '*5,' 4. Convert an Array (Binary Tree) to a Max-Heap.')
    print(' '*5,' 5. Add New Node to the Binary Tree.')
    print(' '*5,' 6. Delete a Node From the Binary Tree.')
    print(' '*5,' 9. Exit.')

    user_choice = input("\n Select from the Menu: > ") 

    return user_choice


# This is the Main application body.
while True :

    user_select = main_menu()

    if user_select == '1' :
        print(' Enter the Binary Tree as a Array.') 
        arr = create_array_node_b_node()
        
    if user_select == '2' : 
        try:
            print_bt_text (arr)
        except :           
            input('\n   You Must First Enter/Create the Array... Press any key then Select Option 1. > ')
    
    if user_select == '3' :
        print(' Check if the Array is a Max Heap.') 
        
        
    if user_select == '4' :
        print(' Convert an Array (Binary Tree) to a Max-Heap.') 


    if user_select == '5' :
        print(' Add New Node to the Binary Tree.') 
        #add_node(arr)

    if user_select == '6' :
        print(' Delete a Node from the Binary Tree.') 
        #delete_node(arr)

    if user_select == '9' :
        print('\n\n   Thank you for using this Appliation. ')
        input('\n         Press any key .. ')
        break
    


Next we will write the function def create_array_node_b_node() in this function the user will start to enter the nodes in the Heap Tree starting from the Root and level-by-level. With every/each Node if the user just press Enter the Node will be as None,then will ask the user if there is any more nodes in the level and if the user answer with [N] then we will complete the level with None. Also in starting of each level we will ask the user if there is any more Nodes remain in the level.
Here is the code ..

ali radwani ahradwani.com python code algorithm heap sorting project



In the last Function in this part, we will print-out the Heap-Array as text of Parents and Childs. Here is the code ..

 # Function to print-out the Heap-Array Tree

def print_bt_text (arr):
    """
        Function will Write/Print-out the Tree as Text Showing the Parents and the Childs.
        
        Arguments: The Array as arr
        
        return None  
    """    
    os.system('clear')
    header()
    print("\n\n==========[ Print out the Binary Tree. {Text Mode} ]==========\n\n")
    
    print('   The array we Have is: ',arr)
   
    for x in range (0,len(arr)):
        print(' ')      
        if arr[x] != None :
      
            try:  # For left childs
                l_child = 2 * x + 1
                
                if arr[l_child] != None :
                    print(f'   Parent Node ({arr[x]}) has a Left Child ({arr[l_child]})',end="") 
                    
                elif arr[l_child] == None:    
                    print(f'   Parent Node ({arr[x]}) has NO Left Child',end="")    
            except:
                pass
                
            try:   # For right Childs
                r_child = 2 * x + 2
                
                if (arr[l_child] == None) and (arr[r_child] != None) :
                    print(f' But it Has a Right Child ({arr[r_child]}).')
        
                elif (arr[l_child] != None) and (arr[r_child] != None) :
            
                    print(f' and a Right Child ({arr[r_child]})')
                    
                elif (arr[r_child] == None):
                    print(f' and Has NO Rigth Child.')
            except:
                pass
                
    input('   DONE ... Here is a Print out of the Heap Tree Array in {Text Mode}')



We will stop here in this part and will do more Functions in Part 3

..:: 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

Python Sorting Algorithm – Heap Sorting -P1


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

[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.]

Once I start preparing and writing the code for Heap Sorting I fond that I can’t jump to the Heap Sorting without some introductions, So in this post we will cover the Array, Binary Tree, Binary Array, Max-Heap, how to know if a given Array is in Max-Heap or not, Add node to a Max-Heap and Delete a node from a Max-heap. For all this, we will have two or three posts to cover what i think we must know.

So First:
Binary Tree: A Binary Tree is a set of Nodes and each Node may have a Maximum of TWO Childs, called Left-Child and Right-Child. Going down to the next level, each of the Child’s (the left one and the right one) again may have TWO Child’s (Left and Right) .. and so on. The last level were there is no more child’s that level is the Leaves. Here are some sample of Binary Tree’s..



All the above are Binary Tree’s, But we will talk about Three Definitions for a Binary Trees:

Full Binary Tree, Complete Binary Tree, Perfect Binary Tree

Full Binary Tree:
A Tree is a Full Binary Tree in which Every/All Nodes Except Leaf Nodes(last level) have Zero or Two Children.

Complete Binary Tree:
A Binary Tree called a {complete binary tree} in which All/Each levels are completely filled except possibly the last level has all keys as left as possible
Practical example of Complete Binary Tree is Binary Heap.

Perfect Binary Tree:
A Binary Tree is {a Perfect Binary Tree} IF all the internal nodes have Two children and all leaf nodes are at the same level.

NOTE: Every Full Binary Tree is A Complete.

FULL BINARY TREEali radwani ahradwani.com python code heap sorting binary tree FULL BINARY TRTEEali radwani ahradwani.com python code heap sorting binary tree
COMPLETE BINARY TREEali radwani ahradwani.com python code heap sorting binary tree COMPLETE BINARY TREEali radwani ahradwani.com python code heap sorting binary tree
PERFECT BINARY TREEali radwani ahradwani.com python code heap sorting binary tree PERFECT BINARY TREEali radwani ahradwani.com python code heap sorting binary tree Figure 1


Binary Tree And Array: To convert a binary tree into array or to present a Binary Tree as an Array we need to consider the following :
1. To Taking all the elements in the Binary Tree.
2. To Keeping the relations between the nodes, who is the parent and what are the childerns for each parents [Left child and Right child].

1. Taking all the elements in the Binary Tree:
So for a given tree as Figure 1:[in above example] , we can see that (A) is the First Element [Root] (First Parent) and has 2 childs (B) (Left Child) & (C) (Right Child), –> Then Element (B) as parent has Two childs (D) (Left Child) & (E) (Right Child), –> Then Element (C) as parent has Two Childs (F) (Left Child) & (G) (Right Child) .. this is the end of the tree, leaves level.

Now, IF we want to present this Tree as an Array we will start with (A) in index 0, then will write all the elements level by level, from Left to Right. So we will have the array a1 as follow:
a1 = [A,B,C,D,E,F,G]

2. Keeping the relations between the Nodes: Using the Method of filling the Array as in point One (above) we Save the relations between the Parents and Childs. For a given Array a1 = [A,B,C,D,E,F,G] we can user three formulas to know the Parent and the Childs of any given Node as following:
Assuming we are at index (x) then:
1. Left Child Index of Node (x) : 2 * x + 1
2. Right Child Index of Node (x) : 2 * x + 2
3. Parent Index of Node (x) : x//2 (absolute value of the division)

So, if we refer to a1 Array and (Figure-1), and say we want to know the childrens of node (A), Node (A) is in index [0] so:
The Left child index of Node (A) is : 2 * 0 + 1 = 0 + 1 = 1, the Element in index 1 in the Array a1[1] = B.

The Right child index of Node (A) is : 2 * 0 + 2 = 0 + 2 = 2, the Element in index 2 in the Array a1[2] = C.

The Left child index of Node (C) is : 2 * 2 + 1 = 4 + 1 = 5, the Element in index 5 in the Array a1[5] = F.

The Right child index of Node (C) is : 2 * 2 + 2 = 4 + 2 = 6, the Element in index 6 in the Array a1[6] = (G).

The Parent of Node (E) will be: 4//2 = 2, so the parent of the Element (E) is a1[2] = (B)

Heap Tree: Is a Binary Essentially an almost Complete Tree. So a Heap Tree is: Tree with All/Each levels are completely Filled except possibly the last level has all keys as left as possible. In Heap The Nodes represents as Integer Numbers.

Max-Heap: In Max-Heap Tree the Child Node is Smaller than his Parent.

Mini-Heap: In Mini-Heap Tree the Child Node is Larger than his Parent.

ali radwani python code math sorting algorithm Heap



We will stop here in this part and will start doing some coding in Python Sorting Algorithm – Heap Sorting – P2.

..:: 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