I am trying to implement my own PriorityQueue class from scratch (not using any existing Java imports or libraries). I know that I want to use a min-heap Data Structure. But I visualize a heap as a form on Binary Search Tree. Should I be using Linked List style Nodes to implement this min-heap, or should I use an an array? What are the benefits or preferred method of either? Or is there a third option available that I could use?
2 Answers
Before answering the question, please see this.
But I visualize a heap as a form on Binary Search Tree.
This is not true. Heap is a form of binary tree but not binary search tree. Please see Difference between binary tree and binary search tree
Now, to answer your question, I would choose some sort of array form. The reason is I need to calculate my children or my parent with index information frequently when I implement a heap. Usually, it happens with below calculation.
Given n is the index of the current node and index starts from 1(for the simplicity)
- parents index = n/2
- left child index = 2n
- right child index = 2n+1
When you do this with LinkedList.get(n), it is O(n). In ArrayList or array, it is O(1).
Comments
The easiest implementation I can think of would use a LinkedList or ArrayList that keeps itself in sorted order based on priority. Then you remove from front or back of list (depending on how you sort array) when it is time to remove someone from the queue.
