Heap

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.