Tuesday, August 14, 2012

Min-Max Heap - Java Implementation

It is possible to build a Min-Max Heap data structure that will perform the following actions with an efficient time complexity:
- Insert a new item in O(lgn) - Find Maximum key in O(1) - Find Minimum key in O(1) - Delete Maximum node in O(lgn) - Delete Minimum node in O(lgn)
The proposed data structure holds Minimum and Maximum heaps with references to each other. The heaps are built as TreeNode[] array objects which hold a set of TreeNode POJO objects (TreeNode fields are: value, max reference and min reference).
maxHeap - is the Maximum Heap. maxHeap - is the Maximum Heap Heap.java - to hold the Min-Max Heaps and actions:
TreeNode POJO:

5 comments:

Javin Paul said...

By looking at title, I thought its article about Heap space in Java implementation :)

Eran Levy said...

bit confusing but it is the Head data structure :)

Peixoto Alves said...

error in
maxHeap=convertArrToTreeNode(arr);
minHeap=convertArrToTreeNode(arr);

help me :)

Eran Levy said...

You need to convert each one of the given array elements to the TreeNode pojo

Anthony Shih said...

In your insert method, wouldn't it be impossible to insert the new node at index[heapSize]? maxHeap and minHeap would be the same size as your initial array built in buildheap, so how can you insert another node at an index 1 higher than the ones in the other heaps?