Binary heap

A binary heap is a data structure in computer science for the efficient sorting of elements. The asymptotically optimal sorting algorithm heapsort uses a binary heap as a central data structure. Further, the binary heap for implementing a priority queue, in which the element with the highest priority can be retrieved and removed efficiently used. The priority of the items will be impressed by this key. Must therefore be on the set of keys are a total order, such as the less-than relation ( < ) is over the integers.

In the literature, the addition is often omitted binary, so that depending on the context of the heap as archetypal ( binary ) heap structure (implemented in an array ) or the class of all heap data structures is meant. Furthermore, when used of the order relation, or a heap as min - heap and max-heap. Because different operations in the min and max heap only by the order relation used, in the following, the binary heap and the operations defined on the example of the min - heap.

Definition Min- Heap

A binary tree is a min - heap, if for each node:

Where the parent node of returns.

This property is referred to as a (min ) heap property.

A heap is therefore a partially ordered tree. There is an order between child and parent node, but the children nodes are not ordered among themselves.

Operations

A binary heap can be efficiently constructed in linear time, and the number of elements from the input denoted. The following operations are working on a heap and have a worst-case running time of:

• Insert - inserts a new element into the heap
• Remove - removes an element
• ExtractMin - extracted the element with the smallest key
• Decreasekey - decreases the key value of an element

The operation getMin returns the smallest element in the heap and therefore requires constant computational effort.

Structure

A binary heap consists of a binary tree in which all the layers must be completely filled up to the last. The last layer of the tree must be padded on the left -justified. This structure ensures that the tree is balanced.

In addition, the binary tree must satisfy the heap condition: the example of the min - heap ( see figure) has the key of each child of a node be greater than or equal to the key of the node itself. The heap property guarantees that the node is always at the root with the smallest key.

Often, a binary heap is not explicitly constructed with pointers, but represented by an array. If you want to store a binary heap in an array, so the root of the tree is stored in the first position in the array. In an array indexing starting with the two successors of a node at the th position of the -th and -th position are stored, according to the Kekule - numbering. Similarly, the successor of the node with index at the -th and -th position are saved when the array indexing starts at 0.

Algorithms

In the analysis of the algorithms the heap size or the number of elements in the heap array is designated.

Heapify

The basis of several heap operations is the function heapify. It provides, where appropriate, the heap condition of a binary tree restores, provided that the left and the right subtree satisfy the heap condition. These heapify exchanges as long as recursively child with parent node until the heap property is no longer violated. In pseudo-code:

Void heapify ( H array, int i)    assert ( isheap (H left, (i)) && isheap (H, right (i )))    int min = i    if ( left ( i) < H.Size H.key && (left (i)) < H.key (min) )      min = left ( i)    if ( right ( i) < H.Size && H.key ( right (i)) < H.key (min) )      min = right ( i)    if ( min! = i) {      H.swap (i, min)      heapify (H, min)    } The auxiliary functions left or right calculate the index of the left and right child node in the heap array, key abstracted from the access to this array and swap exchanges two elements in the array in which the heap is stored. The function traverses the tree only in depth, so that their life is in. Since the height of the tree depends on the number of its logarithmic elements function in the worst case requires heapify logarithmic term with respect to the size of the heap, ie. heapify require only a constant number of additional memory cells, since it is recursive tail. This means that the recursion can be manually or automatically replaced by a loop without a stack:

Void heapify ( H array, int a)    int i = a    do {      assert ( isheap (H left, (i)) && isheap (H, right (i))      int min = i      if ( left ( i) < H.Size H.key && (left (i)) < H.key (min) )        min = left ( i)      if ( right ( i) < H.Size && H.key ( right (i)) < H.key (min) )        min = right ( i)      if ( min == i)        break      H.swap (i, min)      i = min    } While ( true) Because of the successive swap (or " pushing " ) of a node in a subtree down the heapify operation is also called sift -down ( " Seven" ) and Sift -down phase.

Build

The build function constructs a heap from an array by iteratively calls the function heapify. It begins with the leaves meet the heap property by definition, and works its way gradually to the root before. This operation is referred to as bottom-up. As a pseudo-code:

Void build ( array a)    if ( a.empty )      return    for (int i = array.size/2-1; i> = 0, - i)      heapify (a, i) From the structure of the binary heap, which is stored in an array, it follows that from position only leaves, or 1 -element heap is stored. That is to say from the bottom layer begins (levels) of the binary tree. Since the tree elements in the array in level -order iteration are stored successively passes in each of the last to the first element of a level.

The term of build is in, which is not directly obvious. Because heapify is in and will be times called. The linear term is specified in the following equation:

Which iterates over the tree height and the number of subtrees on level or the number of children calculated for all nodes of height.

Decrease -Key

If the key of a heap element is reduced, where appropriate, the heap property must be restored to the previous node. The heap property in the children's subtrees of is not changed by the operation decrease -key. decrease -key works as build bottom-up:

Void decrease (array h, int i, newkey )    assert ( isheap (h, 0))    assert ( h.key ( i) > = newkey )    h.key (i) = newkey    while ( i> 0 && h.key ( i) < h.key ( parent ( i))      h.swap (i, parent ( i))      i = parent ( i) insert

The insertion of an element is done by means of insert by the heap array is extended with a new element at the end with the value, then the function decrease with the inserted key is invoked, so that might hurt heap property is restored:

Void insert ( array h, newkey )    assert ( isheap (h))    int i = H.SIZE    h.resize (i 1)    h.key (i) = inf    decrease (h, i, newkey ) The running time is according to

Remove

Removing an element by means remove done by the element to be removed i removed from its position in the heap, and in its place the at the end of the heap exploiting dividend element is set. Then the heap property must be restored at position i. It can occur both that the element at position i is greater than its parent node, and that it is smaller. Accordingly, it must be moved up or down by means of heapify decrease.

The decrease - case may not be obvious. Why should the former last element of the array to be smaller than a much higher up in the tree deleted item? The reason is that a heap only a partial and not total order represents. Looking at the first common ancestor of the erased and the last element, so it may be that in a subtree with the last element are very small elements, whereas the other subtree contains more elements to the one to be deleted. Here is an example of such a situation. The element with index 5 is to be deleted:

H1 = [0, 1, 2, 2, 1, 2, 2, 2, 2, 1 ] / / is a correct heap -> [ 0, 1, 2, 2, 1, 1, 2, 2, 2, 2 ] / / after the swap with the last element -> [0, 1, 2, 2, 1, 1, 2, 2, 2 ] / / after the removal of the now last element

After removing the last element that violates now at index 5 exploiting dividend element 1 together with its parent node 2, the heap property. A Applying heapify would not change the array, since the function only pushes elements down. For index 5 but it is already a leaf node. Instead, we must push the element at position 5 upwards. This happens with decrease of the function.

Element remove ( array h, unsigned int i)    assert ( isheap (h))    assert ( i < H.SIZE )    removedItem = h [i ]    int lastIdx = H.SIZE -1    h.swap (i, lastIdx )    h.resize ( lastIdx ) / * In the case of i == lastIdx the heap property by the removal was      maintain the element and i is now '' out of bounds '',      because the array has been reduced in size. A call to heapify or      decrease would lead to a crash. * /    if ( i! = lastIdx ) {      if ( i == 0 | | h.key ( i) < h.key ( parent ( i ))) {        heapify (h, i)      Else { }        decrease (h, i) / / decrease does not matter if h.key (i ) == h.key ( parent ( i))      }    return removedItem Extract -Min

Returning and removing an element using extractMin designed similarly to remove. The minimum element is because of the heap condition at the root of the tree and thus represents the element to be removed:

ExtractMin element (array H)    assert ( isheap (H))    assert ( H.Size > 0)    return remove ( H, 0) The running time is according to:

Get- Min

The getMin is the smallest element back into a heap. From the heap property follows directly that the smallest element is always at the first array position, ie the root of the binary tree. In pseudo-code:

GetMin element (array H)    assert ( isheap (H))    assert ( H.Size > 0)    return h.key ( 0) The running time is according to constant: