Heap sort, Data Structure & Algorithms

Assignment Help:

We will start by defining a new structure called Heap. Figure 3 illustrates a Binary tree.

1345_Heap Sort.png

Figure: A Binary Tree

A complete binary tree is said to assure the 'heap condition' if the key of each node is greater than or equal to the key in its children. Therefore the root node will have the biggest key value.

Trees can be represented such as arrays, by first numbering the nodes (beginning from the root) from left to right. Then the key values of the nodes are assigned to array positions whose index is specified by the number of the node. For example, the corresponding array is depicted in Figure

444_Heap Sort.png

                                  Figure: Array for the binary tree of figure

The relationships of a node can also be found out from this array representation. If a node is at position of j, its children will be at positions 2j & 2j + 1. Its parent will be at position +J/2+.

Assume the node M. It is at position 5. Therefore, its parent node is at position

5/2+ = 2 that means the parent is R. Its children are at positions 2 × 5 & (2 × 5) + 1, that means 10 + 11 respectively that means E & I are its children.

A Heap is a complete binary tree, wherein each node satisfies the heap condition, represented as an array.

Now we will study the operations possible over a heap and see how these can be combined to produce a sorting algorithm.

The operations on a heap work into 2 steps.

1. The needed node is inserted/deleted/or replaced.

2. The above operation may cause violation of the heap condition thus the heap is traversed and modified to rectify any such kind of violations.

Examples: Assume the insertion of a node R in the heap 1.

1. Initially R is added as the right child of J & given the number 13.

2. However, R > J. hence, the heap condition is violated.

3. Move R up to position six & move J down to position thirteen.

4. R > P. thus, the heap condition is violated still.

5. Swap R & P.

4. Now the heap condition is satisfied by all nodes to get the heap of Figure

629_Heap Sort1.png

624_Heap Sort2.png

Figure: A Heap

This algorithm is guaranteed to sort n elements within (n log2n) time.

First we will see two methods of heap construction and then elimination in order from the heap to sort the list.

1. Top down heap construction

           • Add items into an initially empty heap, satisfying the heap condition at all steps.

2. Bottom up heap construction

            • Build a heap along the items in the order presented.

            • From the right most nodes modify to satisfy the heap condition. We will reveal this with an example.

 Example: construct a heap of the following using top down approach for heap construction.

                                        PROFESSIONAL

Figure illustrates different steps of the top down construction of the heap.

888_Heap Sort3.png

Figure: Heap Sort (Top down Construction)

Example: The input file is (2,3,81,64,4,25,36,16,9, 49). While the file is interpreted as a binary tree, it results in Figure. Another Figure shows the heap.

666_Heap Sort4.png

Figure: A Binary tree                   Figure: Heap of figure

Given figure illustrates several steps of the heap of above Figure as the sorting takes place.


Related Discussions:- Heap sort

Recurrence relation, solve the following relation by recursive method: T(n...

solve the following relation by recursive method: T(n)=2T(n^1/2)+log n

What do you understand by tree traversal, What do you understand by tree tr...

What do you understand by tree traversal? The algorithm walks by the tree data structure and performs some computation at everynode in the tree. This process of walking by the

2 way merge sort, merge sort process for an example array {38, 27, 43, 3, 9...

merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the

Insertion sort, Data array A has data series from 1,000,000 to 1 with step ...

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Algorithams example, any simple algoritham questions with answers

any simple algoritham questions with answers

Implement an open hash table, In a chained hash table, each table entry is ...

In a chained hash table, each table entry is a pointer to a collection of elements. It can be any collection that supports insert, remove, and find, but is commonly a linked list.

Graphs with negative edge costs, We have discussed that the above Dijkstra'...

We have discussed that the above Dijkstra's single source shortest-path algorithm works for graphs along with non-negative edges (like road networks). Given two scenarios can emerg

Algorithm to sort a given list by quick sort method, Q. Write down an algor...

Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

In-order traversal, Write steps for algorithm for In-order Traversal Th...

Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion

Algorithm for dfs, Step 1: Choose a vertex in the graph and make it the sou...

Step 1: Choose a vertex in the graph and make it the source vertex & mark it visited. Step 2: Determine a vertex which is adjacent to the source vertex and begun a new search if

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd