Heap Operations
Operations | Running Time |
---|---|
DeleteMax/ExtractRoot: | O(logn) |
Query Top(Max/Min): | O(1) |
InsertElement: | O(logn) |
Heapify: | O(logn) |
Build Heap: | O(nlogn) |
Find K Ordered Top(Min/Max) Elements: | O(klogn) |
File's Descriptions:
1) Heap / src / com / heap / Heap.java:
The library importing which you will be able to use all the Heap operations with the above mentioned Running Times
2) Heap / src / com / heap / MaxIntegerComparator.java:
This Comparator can be used if a MaxHeap is needed.
3) Heap / src / com / heap / MinHeapComparator.java:
This Comparator can be used if a MinHeap is needed. The TestHeap.java uses this Comparator to create a MinHeap and performs several Unit Tests.
4) Heap / src / com / heap / Node.java:
The Heap basically contains the Objects of this class. Currently it has only value field, you can have several other instance variables as satellite data of your Node. The Heap will be managed based on the this.value variable.
5) Heap / src / com / heap / StringComparator.java
This Comparator can be used to arrange the Strings lexicographically. The TestHeap.java uses this Comparator to manage a Heap of Strings and also performs several Unit Tests on it.
6) Heap / src / com / heap / TestHeap.java
This class has the main method and creates two Heaps (Min-Heap and String-Heap). It also performs certain unit tests. This can be refered to implement the library.
7) Heap / src / com / heap / UnitTests.java
This class has certain Tests and prints an error if the result is not as desired.