1. <programming> An area of memory used for dynamic memory allocation where blocks of memory are allocated and freed in an arbitrary order and the pattern of allocation and size of blocks is not known until run time. Typically, a program has one heap which it may use for several different purposes.
2. <programming> A data structure with its elements partially ordered (sorted) such that finding either the minimum or the maximum (but not both) of the elements is computationally inexpensive (independent of the number of elements), while both adding a new item and finding each subsequent smallest/largest element can be done in O(log n) time, where n is the number of elements.
Formally, a heap is a binary tree with a key in each node, such that all the leaves of the tree are on two adjacent levels; all leaves on the lowest level occur to the left and all levels, except possibly the lowest, are filled; and the key in the root is at least as large as the keys in its children (if any), and the left and right subtrees (if they exist) are again heaps.
heap[i] <= heap[2*i] and heap[i] <= heap[2*i+1] for all i,