Heap (data structure)

A heap (English literally: heap or heap ) in computer science is mostly based on trees abstract data structure. In a heap objects or elements can be stored and removed from it again. They are used so that the storage of quantities. The element is a key assigned to that determines the priority of the elements. Often, the elements themselves are used as a key.

Therefore must have the set of keys a total order be set over which the order of the inserted elements is specified. For example, the set of integers act together with the Little relation ( < ) as the key quantity.

The term heap is often understood as meaning equal to a partially ordered tree (see the following diagram illustrating an example of a min - heap). Occasionally, one sees only a particular implementation of restrictive form of a partially ordered tree, namely embedding in an array, a heap.

Use find heaps especially where it matters to take an element with the highest priority from the heap quickly ( HIFO principle), such as priority queues.

Operations

Depending on the type support a range of operations heaps. The main operations are

In addition, are often also the operations CHANGEKEY to adjust the key and merge for merging two heaps provided. The operation CHANGEKEY is often formed by the succession execution of the operations insert and remove, being adjusted after removing and before reinserting the key. In some cases, Heaps offer CHANGEKEY instead of only the operation decreasekey, in which the key can only be reduced.

Heap condition

A distinction heap in min heap and max- heap. When Min- heap is defined as the property that the key of the children of a node are always greater than the key of her father when heap condition. This causes at the root of the tree is an element with minimum key is always to find the tree. Conversely requires the heap condition at Max Heaps that the keys of the children of a node are consistently smaller than that of her father. Here is always at the root of the tree is an element with maximum key.

Mathematically, the difference between the two variants only in its opposite order of the elements. Since the definition of ascending and descending is purely arbitrary, so it is a question of interpretation whether it is a min - heap or a max-heap with a concrete implementation.

Often it also happens that a heap is intended to reflect the heap property in both directions. In this case, just two heaps created, with the orders one by Little and the other to the greater-than relation. Such a data structure is then called Doppelheap or short Deap.

When using double - Heaps is important to note that not every implementation of the heap while maintaining their runtime behavior for the individual operations. For example, support Fibonacci heaps just a decreasekey to reduce the key with amortized constant maturity. A more general CHANGEKEY to change the key, which would be required in the event of such a double - heap, but needs at least logarithmic amortized runtime.

A variant of the heap, which supports the heap condition is limited or in a modified form, are so-called min-max heap. It is double - heaps that can abide by the modified form of the heap condition, the data in only one tree.

Variants of heaps

There are numerous types of heaps with different good runtime characteristics for the various operations they provide. Examples of heaps are:

• Binary heap Min-max heap

There is also a variant with soft heaps in a better run-time behavior is achieved by a certain portion of the key may be corrupted. These depraved key no longer have their original value.

Runtime behavior of different types of heap

The following table gives the worst-case running times of various heap in terms of their operations.

Application

Heaps have a wide range of applications. Often, especially in the use of priority queues, as they are needed with servers or operating systems to determine the execution order of tasks.

There are, however, applications which are not specifically require the use of queues. In general terms, a heap is an ideal data structure for greedy algorithms to make the progressive local optimized decisions. Thus, a binary heap is used for sorting, for example, in the sorting algorithm heapsort. Fibonacci heaps can be accessed by Dijkstra's algorithm or Prim application.