Ali's Photography Space…

[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 TREE	FULL BINARY TRTEE
COMPLETE BINARY TREE	COMPLETE BINARY TREE
PERFECT BINARY TREE	PERFECT 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.

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