COMPLETE BINARY TREE:- A binary is said to be complete binart tree if it has the maximum number of opssible nodes at each level except the last one .
HEAP TREE:- Heap is a complete binary tree. There are two types of heap.
1. Max heap:- A complete binary tree is called a max heap if the value present at any node is greater than or equal to the value of each of its child nodes.
2. Min heap:- A complete binary tree is called a min heap if the value present at any node is lesser than or equal to the value of each of its child nodes.
HEAP SORT
Heap sort is one of most widely used sorting techniques.In this technique,we are given a list,say A with N elements.
=> First of all construct a heap.
=> Now,exchange the root element of heap with its last element I.e. the Nth element.(lat the heap be max heap).now,the largest element is placed at the end of the list .this element is sorted.
=> Reconstuct the heap,using unsorted elements i.e. N-1 elements.
=> Again,exchange the root element of heap with its last element i.e.(N-1)th element.now,the last two elements are in sorted form.Reconstruct heap using N-2 elements and so on.
=> This process is repeated until the entire list is sorted.
1. Max heap:- A complete binary tree is called a max heap if the value present at any node is greater than or equal to the value of each of its child nodes.
Heap sort is one of most widely used sorting techniques.In this technique,we are given a list,say A with N elements.
=> First of all construct a heap.
=> Now,exchange the root element of heap with its last element I.e. the Nth element.(lat the heap be max heap).now,the largest element is placed at the end of the list .this element is sorted.
=> Reconstuct the heap,using unsorted elements i.e. N-1 elements.
=> Again,exchange the root element of heap with its last element i.e.(N-1)th element.now,the last two elements are in sorted form.Reconstruct heap using N-2 elements and so on.
=> This process is repeated until the entire list is sorted.
No comments:
Post a Comment