Heap (data structure)

In computer science, there is a data structure called a heap. (There's also something

else called a heap, which is memory that can be dynamically allocated; the two are unrelated.)

The heap data structure is a binary tree in which the value stored at each node is no less

than the value stored at either of its two children.

A heap is one way to implement a priority queue and is used in the heapsort

sort algorithm.

Heaps are commonly represented by arrays of values; the root of the tree is item 1 in the

array, and the children of the item n are the items at 2n and 2n+1; so item 1's

children are items 2 and 3, 2's children are items 4 and 5, etc. This allows you to regard any

1-based array as a possibly-screwed-up heap.

        1         

       / \        

      /   \       

     2     3      

    / \    /\     

   4   5  6  7    

  /\   /\         

 8  9 10 11       

If you regard the array as a screwed-up heap, you can fix it in O(n) time by restoring the heap property from

the bottom up. Consider each trio containing a node and its two children, starting from the end of

the array; if the greatest value of the three nodes is not in the top node, exchange.