Changes by last author:
Added:
|
Study material for developers
Heap is a binary-tree data structure stored in an array. The key of the parent is always (kept) smaller or equal to the key of any of its children. Therefore the smallest key element is always at the root of the tree. If you always need the smallest-key element (like the key is a time instant, and you process chronologically) this is a very simple and fast operation. Scientifically speaking insert and delete operations cost is log(n). If you have million elements in a heap, delete or insert operation is just 10 times more time than if you have a few elements. Cool, isn't it? The index of the parent is int(x/2) if x is the index of the child. The root index is 1. (some implementations subtract 1 from indexes, so the root index is 0). See the OnlineCourse/EventQueue for an application of the heap data structure. There is a new proposal from David about a little faster, asm based heap: |