Is it possible to implement a heap without knowing the size of the input beforehand?

Question

Say, I have a continuous input of integers of unknown size. At any instant in time, upon receiving k elements as input, I would like to have a heap of size k. How can this be achieved without initializing an array of some length beforehand?

Answer 1

With binary tree based heap. You do not need to know the Limits on size.

http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html

Even with array-based implementation, you can use the doubling of allocated size trick when capacity falls short. It will have same time complexity.

Use ArrayList

why use ArrayList?

Answer 2

The underlying data-structure of java.util.PriorityQueue is a heap. I assume by mentioning heap you meant to have ordering functionality on your data.

When you initialize a PriorityQueue using default constructor, it creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering. If you define a custom Comparator, it will order according to your constraint.

Other dynamic size data-structure like ArrayList won't provide the functionality of sorted order unless you sort them own-self.

I think you want to solve something similar to k'th smallest/largest element of a running stream. If yes, you can initialize PriorityQueue with default constructor and on pushing each element check if its current size is k. if it's current size is k, replace top element with new element according your constraint.

And last of all, use ArrayList if you only need dynamic size and don't need ordering like heap.