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:
- 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:
By looking at title, I thought its article about Heap space in Java implementation :)
bit confusing but it is the Head data structure :)
error in
maxHeap=convertArrToTreeNode(arr);
minHeap=convertArrToTreeNode(arr);
help me :)
You need to convert each one of the given array elements to the TreeNode pojo
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?
Post a Comment