Binary heap: Difference between revisions

Revision as of 20:32, 9 July 2004

Revision as of 19:38, 16 July 2004

Line 15:

Binary heaps are also commonly represented by [[array]]s of values. For example, the root of the tree could be item 0 in the array, and the children of item ''n'' are the items at 2''n''+1 and 2''n''+2; so item 0's children are items 1 and 2, 1's children are items 3 and 4, etc. This allows you to regard any 1-based array as a possibly-screwed-up heap.

The fact that we retrievingRetrieving the maximum/minimum element from a heap is the basis for the [[heapsort]] algorithm. Also note that the ordering of siblings in a heap is not specified by the [[heap|heap property]], so the two children of a parent can be interchanged.

== Heap operations ==