Heap search algorithm with java code

HEAPS



The (binary) heap data structure is an array object that we can view as a
nearly complete binary tree Each node of the tree corresponds to an element of the array. 
The tree is completely filled on all levels except possibly the lowest, which is filled from the
left up to a point. An array
A that represents a heap is an object with two attributes: 
A:length, which (as usual) gives the number of elements in the array, and A:heap-size
which represents how many elements in the heap are stored within array A


Apart from being a useful data structure heaps could also sort the numbers in a efficient way.
Following is an example of a Heap. As in a max-heap the max element is the root node.
We could remove the top element and then rebuild heap. And then remove the next max
element. There by getting the array in sorted order

An image of a heap and its corresponding array representation.

The heap property naturally lends itself to the following parent , left and right child 
by using array indexes.

Calculate the indexes of right, left, and parent in a heap

An element can be searched in a heap in a way similar to the way in a binary search tree.
The following is an algorithm to search an element in a min-heap recursively.
If the root node element is greater than the element to be searched. Then the element
to be searched cannot be in the left subtree. So we search only the right subtree.
This gives a huge improvement over the searching for all elements in a linear way.
The following is a java code that does the same - 


Algorithm to search an element inside a min-heap


There is an important property of heap that is to be maintained. That is the element at the
root of the subtree must be the maximum element for a max-heap and minimum for a 
min-heap. This porperty holds for any subtree of a heap.
When this property is broken we could use the heapify function to correct it.
Following is a pseudocode version of it.




                       
REFERENCES:
1. Introduction To Algorithm - Cormen


Comments

Popular posts from this blog