One thing that maybe could be added here would be a constructor that heapifies an existing array.
The MOST remarkable thing about a heap is that you can create a heap of N UNORDERED elements in O(N) time (rather than the expected O(NlogN) time if you insert one by one).
So it's a pity to create a heap data structure without the "heapify" functionality (that is not hard at all to implement).
It's what makes Heaps preferable to other Priority Queue implementations such as Binomial Trees (unless you're merging PQs.. in such a case the Binomial Trees would be better because of their O(logN) merges).
This is a great point, and I’ll use your suggestion when I build on this article later. For this article I wanted to focus on the basics and it was starting to get lengthy. Thank you for the suggestion!
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
One thing that maybe could be added here would be a constructor that heapifies an existing array.
The MOST remarkable thing about a heap is that you can create a heap of N UNORDERED elements in O(N) time (rather than the expected O(NlogN) time if you insert one by one).
So it's a pity to create a heap data structure without the "heapify" functionality (that is not hard at all to implement).
It's what makes Heaps preferable to other Priority Queue implementations such as Binomial Trees (unless you're merging PQs.. in such a case the Binomial Trees would be better because of their O(logN) merges).
This is a great point, and I’ll use your suggestion when I build on this article later. For this article I wanted to focus on the basics and it was starting to get lengthy. Thank you for the suggestion!