Trees and Heap Sort

• Introduction

A tree is a type of recursive data structure and can be defined as a non-linear data structure connecting elements in levels or hierarchy. Trees are used to store information in hierarchical order.

Fig. 1- Tree

• Properties of Tree

It is an undirected acyclic graph. There is always a root node in a tree that is specific like in fig.1, we have A as the root node. The tree consists of nodes that store the data and are linked in levels. The nodes having a superior node are known as the child nodes of that node and the superior node is a parent node of that node. Like in fig.1, K and L are child nodes of E and E is the parent node of K and L. Each child can have only one parent but each parent can have multiple children. If a tree has N nodes, there will be an N-1 number of edges.

There are six types of trees in data structures namely General Tree, Binary Tree, Binary Search Tree, AVL Tree, Red-Black Tree, N-ary Tree.

• Binary Tree

It is a type of tree where each parent node can have atmost two children i.e. either 0, 1, or 2 children. The child nodes are branched into the left child node and right child node.

Fig. 2- Binary Tree

In fig.2, Node 1 is the root node and 2 and 3 are its children. Node 2 is the parent node of 2 child nodes i.e. 4 and 5. Node 3 is the parent node of 1 child node i.e. 6. Hence, it is a Binary Tree.

There are five types of Binary Tree namely Rooted Binary Tree, Full/Strictly Binary Tree, Complete/Perfect Binary Tree, Almost Complete Binary Tree, Skewed Binary Tree.

This is the initial code of application of Tree-

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

• Binary Search Tree

A binary Search Tree (BST) is an example of a rooted binary tree and is also called an Ordered Binary Tree. In this, the nodes in the left subtree are lesser in value than the root node and the nodes in the right subtree are greater in value than the root node. It makes the comparison easier among the nodes easier.

• Tree Traversal Techniques

Tree Traversal is defined as visiting all the nodes of a tree. There are many ways to traverse a tree. A tree can be traversed by the Breadth-First Traversal technique or the Depth-First Traversal Technique. We will discuss the Traversal techniques that fall under Depth First Traversal Technique. There are three ways in this technique and they are-

Fig. 3-Tree Traversal

Preorder

First, visit the root node.

then, traverse the left sub-tree.

and then, traverse the right sub-tree

In fig.3, Preorder would be — 1 12 5 6 9

Preorder generally gives us a copy of the given tree and also helps in finding the prefix expression of the tree.

Inorder

First, traverse the left sub-tree.

then, visit the root node.

and then, traverse the right sub-tree

In fig.3, Preorder would be — 5 12 6 1 9

Inorder gives us the non-decreasing or non-increasing order of a Binary Search Tree (BST).

Postorder

First, traverse the left sub-tree.

then, traverse the right sub-tree.

and then, visit the root node.

In fig.3, Preorder would be — 5 6 12 9 1

Postorder generally helps in deletion operation while using a tree and also provides a postfix expression for the tree.

• Heap Sort

A sorting technique that is comparison-based and uses Binary Heap Data Structure. It is used to sort a given set of elements by making a systematic binary heap by heapifying it and then using heap sort methods to sort it.

The Heap can be of two types- Maximum Heap and Minimum Heap

For example, let us take an array — 1, 12, 9, 5, 6, 10.

Fig. 4- Maximum Heap Tree and Minimum Heap Tree

Maximum Heap

In this, as the name suggests, the maximum element is pushed to be the root node. When Heap sort is applied to the maximum heap tree, the array is obtained in ascending order.

Minimum Heap

Here, the minimum element is the root node and the maximum element is pushed down to be a leaf node. When Heap sort is applied to the minimum heap tree, the array is obtained in descending order.

• Properties of Heap Sort

Heap Sort uses a complete binary tree as it is organized and space-efficient. It is also called the “In-place algorithm” and is one of the most efficient sorting methods as it is similar to selection sort. We can obtain the array in both ascending and descending order depending on the type of heap formed. Descending if it is a minimum heap tree and ascending if it is a maximum heap tree. If there is a parent node at the given index ‘k’ then, the left child of the node can be represented as ‘2*k + 1’ and the right child of the node can be represented as ‘2*k + 2’.

Now, let us see how heap sort works in a maximum heap.

The processes involved are-

SWAP — The root node containing the largest element is replaced by the leaf node.

REMOVE — After the replacement, the leaf node (the largest element) is removed from the tree and is placed at the required position in the array.

HEAPIFY — The resultant heap after swap and remove will be again heapified to get the largest element on the top.

The same process of replacing the root node with leaf nodes and removing the leaf node (sorting it out in the array) and heapifying the tree will take place and in the end, we will get the sorted array.

Fig. 5- Heap Sort

• Time Complexity

The time complexity of the Heap Sort is as follows

1. Best Case — O(n logn)
2. Average Case — O(n logn)
3. Worst Case — O(n logn)

• Applications of Heap Sort

They are used in Priority Queue implementation. Dijkstra’s algorithm and Prim’s algorithm also take help of heap data structure and there are many other uses of Heap Sort as it has a lesser worst-case time complexity than other competitive sorting algorithms.