Data structures: binary heap

Binary heap (binary heap) - simply implemented data structure that allows you to quickly (in logarithmic time) add elements and extract the element with the maximum priority (for example, the maximum value).

For further reading it is necessary to have an idea about the trees , and also it is desirable to know about the estimation of the complexity of the algorithms . Algorithms in this article will be accompanied by a C # code.

Introduction

Binary heap is a complete binary tree, for which the main property of the heap is fulfilled: the priority of each vertex is higher than the priorities of its descendants. In the simplest case, the priority of each vertex can be considered equal to its value. In this case, the structure is called max-heap , since the root of the subtree is the maximum of the values ​​of the elements of the subtree. For simplicity, this article is used in this article. I also recall that a tree is called complete binary if each vertex has no more than two descendants, and the filling of the vertex levels goes from top to bottom (within one level, from left to right).
')


It is convenient to store a binary heap as a one-dimensional array, with the left descendant of a vertex with index i having the index 2*i+1 , and the right 2*i+2 . The root of the tree is an element with index 0. The height of the binary heap is equal to the height of the tree, that is, log ₂ N, where N is the number of elements in the array.

I will result preparation of a class on C #:

 public class BinaryHeap { private List<int> list; public int heapSize { get { return this.list.Count(); } } } 

Add item

A new element is added to the last place in the array, that is, the position with the index heapSize :



It is possible that this will violate the main property of the heap, since the new element may be larger than the parent. In this case, you should "raise" the new element by one level (change with the top-parent) until the main property of the heap is observed:





In other words, the new element “pops up”, “pushes” upward until it takes its place. The complexity of the algorithm does not exceed the height of the binary heap (since the number of “rises” is not greater than the height of the tree), that is, it is equal to O (log ₂ N).

 public void add(int value) { list.Add(value); int i = heapSize - 1; int parent = (i - 1) / 2; while (i > 0 && list[parent] < list[i]) { int temp = list[i]; list[i] = list[parent]; list[parent] = temp; i = parent; parent = (i - 1) / 2; } } 

Binary heap ordering

In the course of other operations with an already constructed binary heap, the main property of the heap may also be violated: the vertex may become smaller than its descendant.



The heapify method restores the main heap property for a tree with a root in the i-th vertex, provided that both subtrees satisfy it. To do this, it is necessary to “lower” the i-th vertex (change places with the largest of descendants) until the main property is restored (the process will be completed when there is no descendant larger than its parent). It is easy to understand that the complexity of this algorithm is also equal to O (log ₂ N).

 public void heapify(int i) { int leftChild; int rightChild; int largestChild; for (; ; ) { leftChild = 2 * i + 1; rightChild = 2 * i + 2; largestChild = i; if (leftChild < heapSize && list[leftChild] > list[largestChild]) { largestChild = leftChild; } if (rightChild < heapSize && list[rightChild] > list[largestChild]) { largestChild = rightChild; } if (largestChild == i) { break; } int temp = list[i]; list[i] = list[largestChild]; list[largestChild] = temp; i = largestChild; } } 

Build a binary heap

The most obvious way to build a bunch from an unordered array is to add in turn all its elements. The time estimate of such an algorithm is O (N log ₂ N). However, you can build a bunch even faster - for O (N). First, you should build a tree from all elements of the array, not caring about the basic heap property, and then call the heapify method for all vertices that have at least one descendant (since the subtrees, consisting of one vertex without descendants, are already ordered). Descendants are guaranteed to have the first heapSize/2 vertices.

 public void buildHeap(int[] sourceArray) { list = sourceArray.ToList(); for (int i = heapSize / 2; i >= 0; i--) { heapify(i); } } 

Extraction (deletion) of the maximum element

In an ordered max-heap maximum element is always stored in the root. Restore the order of the binary heap after removing the maximum element by placing the last element in its place and calling heapify for the root, that is, ordering the entire tree.

 public int getMax() { int result = list[0]; list[0] = list[heapSize - 1]; list.RemoveAt(heapSize - 1); return result; } 

Binary Heap Sorting

Note that you can sort an array by first building a binary heap from it, and then sequentially extracting the maximum elements. Let us estimate the time complexity of such an element: the construction of the heap is O (N), the extraction of N elements is O (N log ₂ N). Therefore, the final estimate is O (N log ₂ N). In this case, additional memory for the array is not used.

 public void heapSort(int[] array) { buildHeap(array); for (int i = array.Length - 1; i >= 0; i--) { array[i] = getMax(); heapify(0); } } 

Conclusion

Thus, a binary heap has a logarithmic height tree structure (relative to the number of vertices), allowing for the logarithmic time to add elements and extract the element with the maximum priority in constant time. At the same time, the binary heap is simple to implement and does not require additional memory.