Growing with the Web

Binary heap

Published , updated
Tags:

A binary heap is a binary tree data structure that typically uses an array or list as its underlying data structure. Heaps are one of the fundamental data structures that all software developers should have in their toolkit due to its fast extraction of either the minimum or the maximum element in a collection.

Binary heaps come in two flavours; the min-heap which allows O(\log n) extraction of the minimum element, and the max-heap which allows the same for the maximum value. Before it is possible to extract values, the heap must first be constructed. This is done by running an operation called build heap which heapifies the first half of the elements, starting at the middle.

It is typical to implement priority queues using heaps due to their O(\log n) extract min/max time.

For simplicity, the rest of this article will focus on the min-heap.

The animations in this article rely on CSS transforms on SVG which is not yet implemented in Edge.

Time complexity

Operation Description Complexity
Build heap Builds a heap from a binary tree O(n)
Decrease key Decreases an existing key to some value O(\log n)*
Delete Deletes a node given a reference to it O(\log n)*
Extract minimum Removes and returns the minimum value O(\log n)
Find minimum Returns the minimum value Θ(1)
Insert Inserts a new value O(\log n)
Union Combine the heap with another to form a valid binary heap O(n), O(k \log n)**

* With a reference to an index
** Where k is the size of the smaller heap

Properties

A binary heap is a binary tree with the heap property; the value of each node is greater than or equal to its parent.

Representation

There are two main ways of representing a binary tree. The first is using node objects that have references to their children.

Tree representation

The second is using a regular array and manipulating the index of the node to find its children. The index of the left child of a node is 2i + 1 and the index of the right is 2i + 2 where i is the index of the parent.

Array representation

The index of node's parent can also be retrieved with \lfloor(i - 1) / 2\rfloor.

Binary heap vs binary search tree

While a binary heap is a binary tree, it is not necessarily a binary search tree. A binary heap cares about both children being greater than the node, whereas in a binary search tree, the left child is smaller than the node and the right child is larger.

Left children are not necessarily less than the right

Heapsort

Heapsort operates by forming a heap, extracting the min/max item and repeating on the smaller array until everything is sorted. This can be done in-place by first building a heap and then incrementing the start index of the array. Heapsort runs in O(n \log n) time. This algorithm is explained in depth in the Heapsort article.

Operations

Heapify

The heapify operation (often called “sift down”) is used to maintain the heap property; that a node’s children must be greater than the node. It works by checking if the smallest child node is less than the node itself, then swapping it and calling heapify recursively on it.

Binary heap heapify operation example, your browser doesn't support SVG.
Heapify on node 5

Build heap

The build heap operation converts a regular binary tree into a binary heap by running the heapify operation on the first half of the elements, starting from the middle. Building a heap using this operation runs in O(n) time, so it’s more efficient than inserting n times which would run in O(n \log n) time.

Binary heap build heap operation example, your browser doesn't support SVG.

The build heap proof page goes into depth on why this is turns out to be a linear algorithm.

Insert

Inserting an element is performed by adding the item to the heap and then recursively swapping the node with its parent until its parent is less than the node being inserted, this is called to sift up.

Binary heap insert operation example, your browser doesn't support SVG.
Insert on node 2

Find minimum

The minimum is always the head of the list so it’s just a matter of returning the head.

Extract minimum

Since the minimum is always maintained as the head of the list, it’s easy to find. Removing the minimum from the list is a little more involved, it can be done by moving the last element of the heap to the head and then heapifying the head.

Binary heap extract minimum operation example, your browser doesn't support SVG.

Delete

Given a reference to an index (not a key or a node), the delete operation moved the last element in the list to the deleted spot and reduces the list’s size by 1, effectively deleting it from the list. The heap then needs to be adjusted to maintain the heap property so the node either sifts up if the element is less than its parent or it sifts down by calling heapify on the index.

Binary heap delete operation example, your browser doesn't support SVG.
Delete on node 5

Since a reference to an index is required and the fact that delete often isn’t useful in a priority queue, the delete operation is ususally omitted from binary heap implementations. If all you have is a reference to the node or key then the operation becomes O(n) as the index needs to be found by iterating through the list.

Decrease key

Given a reference to an index, the decrease key operation modifies the key of the node and then sifts up if necessary.

Binary heap decrease key operation example, your browser doesn't support SVG.
Decrease key of node 9 to 1

Union

Two simple implementations of the union operation are:

  • To join both underlying lists and then run build heap on the combined list, resulting in a O(n) run time complexity. This would be faster on heaps that are approximately the same size.
  • To insert each element from the smaller heap into the larger one, resulting in an O(k \log n) run time complexity where k is the size of the smaller list. This would be faster on heaps where one is much smaller than the other.

Code

/// <summary>
/// Represents a binary heap data structure capable of storing generic key-value pairs.
/// </summary>
public class BinaryHeap<TKey, TValue> : IPriorityQueue<TKey, TValue>
    where TKey : System.IComparable
{
    /// <summary>
    /// Represents an invalid index that comes from GetParentIndex.
    /// </summary>
    private const int _invalidIndex = -1;

    /// <summary>
    /// The heap's data.
    /// </summary>
    private List<Node> list;

    /// <summary>
    /// Creates a binary heap.
    /// </summary>
    public BinaryHeap() : this(0) 
    {
    }

    /// <summary>
    /// Creates a binary heap.
    /// </summary>
    /// <param name="size">The expected maximum size of the heap. this value reduces the number
    /// of reallocations to the backing List.</param>
    public BinaryHeap(int size) 
    {
        list = new List<Node>(size);
    }

    /// <summary>
    /// Creates a binary heap.
    /// </summary>
    /// <param name="items">A List to initialise the binary heap with.</param>
    public BinaryHeap(List<Node> items)
    {
        list = items;
        BuildHeap();
    }

    /// <summary>
    /// Inserts a new key-value pair into the heap.
    /// </summary>
    /// <param name="key">The key to insert.</param>
    /// <param name="val">The value to insert.</param>
    /// <returns>The inserted node.</returns>
    public INode<TKey, TValue> Insert(TKey key, TValue val) 
    {
        return Insert(new Node(key, val));
    }

    /// <summary>
    /// Inserts a Node into the heap.
    /// </summary>
    /// <param name="node">The node to insert.</param>
    /// <returns>The inserted node.</returns>
    public INode<TKey, TValue> Insert(Node node)
    {
        int i = list.Count;
        list.Add(node);
        SiftUp(i);
        return node;
    } 

    /// <summary>
    /// Extracts and returns the minimum node from the heap.
    /// </summary>
    /// <returns>The heap's minimum node or undefined if the heap is empty.</returns>
    public INode<TKey, TValue> ExtractMinimum() 
    {
        if (list.Count == 0) 
            return null;
        if (list.Count == 1) 
        {
            var ret = list[0];
            list.RemoveAt(0);
            return ret;
        }
        Node min = list[0];
        Node last = list[list.Count - 1];
        list.RemoveAt(list.Count - 1);
        list[0] = last;
        Heapify(0);
        return min;
    }

    /// <summary>
    /// Returns the minimum node from the heap.
    /// </summary>
    /// <returns>The heap's minimum node or undefined if the heap is empty.</returns>
    public INode<TKey, TValue> FindMinimum() 
    {
        if (list.Count == 0)
            return null;
        return list[0];
    }

    /// <summary>
    /// Clears the heap's data, making it an empty heap.
    /// </summary>
    public void Clear() 
    {
        list.Clear();
    }

    /// <summary>
    /// Constructs a heap out of the data list.
    /// </summary>
    private void BuildHeap() 
    {
        for (int i = (int)(list.Count / 2); i >= 0; i--) 
            Heapify(i);
    }

    /// <summary>
    /// Heapifies the binary heap on an index, swapping the element with its smallest child if
    /// it's less than that node and recursing if so.
    /// </summary>
    /// <param name="i">The index to heapify.</param>
    private void Heapify(int i)
    {
        int l = GetLeftIndex(i);
        int r = GetRightIndex(i);
        int smallest = i;
        if (l < list.Count && list[l].CompareTo(list[i]) < 0) 
            smallest = l;
        if (r < list.Count && list[r].CompareTo(list[smallest]) < 0) 
            smallest = r;
        if (smallest != i) 
        {
            Swap(i, smallest);
            Heapify(smallest);
        }
    }

    /// <summary>
    /// Swap two indexes within the list.
    /// </summary>
    /// <param name="i1">The first index to swap.</param>
    /// <param name="i2">The second index to swap.</param>
    private void Swap(int i1, int i2)
    {
        Node temp = list[i1];
        list[i1] = list[i2];
        list[i2] = temp;
    }

    /// <summary>
    /// Gets the index of an index's parent.
    /// </summary>
    /// <param name="i">The index.</param>
    /// <returns>The index's parent.</returns>
    private int GetParentIndex(int i)
    {
        if (i == 0) 
            return _invalidIndex;
        return (i - 1) / 2;
    }

    /// <summary>
    /// Gets the index of an index's left child.
    /// </summary>
    /// <param name="i">The index.</param>
    /// <returns>The index's left child.</returns>
    private int GetLeftIndex(int i)
    {
        return 2 * i + 1;
    }

    /// <summary>
    /// Gets the index of an index's right child.
    /// </summary>
    /// <param name="i">The index.</param>
    /// <returns>The index's right child.</returns>
    private int GetRightIndex(int i)
    {
        return 2 * i + 2;
    }

    /// <summary>
    /// Finds the index of a node. This is an O(n) operation that is used in order to support
    /// operations that are less than typical on binary heaps like Delete and DecreaseKey.
    /// </summary>
    /// <param name="node">The node to find the index of.</param>
    /// <returns>The index of the node.</returns>
    private int FindIndexOfNode(INode<TKey, TValue> node)
    {
        // Searching for the index of node is an O(n) operation
        var castedNode = (Node)node;
        var index = list.IndexOf(castedNode);
        if (index == _invalidIndex)
        {
            throw new ArgumentException("The node is not within the list");
        }
        return index;
    }

    /// <summary>
    /// Decreases a key of a node.
    /// </summary>
    /// </param name="node">The node to decrease the key of.</param>
    /// </param name="newKey">The new key to assign to the node.</param>
    public void DecreaseKey(INode<TKey, TValue> node, TKey newKey)
    {
        DecreaseKeyAt(FindIndexOfNode(node), newKey);
    }

    /// <summary>
    /// Decreases a key of a node.
    /// </summary>
    /// </param name="index">The index of the node to decrease the key of.</param>
    /// </param name="newKey">The new key to assign to the node.</param>
    private void DecreaseKeyAt(int index, TKey newKey)
    {
        if (list[index].Key.CompareTo(newKey) < 0)
            throw new ArgumentOutOfRangeException("New key is larger than old key.");
        list[index].Key = newKey;
        SiftUp(index);
    }

    /// <summary>
    /// Deletes a node.
    /// </summary>
    /// <param name="node">The node to delete.</param>
    public void Delete(INode<TKey, TValue> node)
    {
        DeleteAt(FindIndexOfNode(node));
    }

    /// <summary>
    /// Deletes a node.
    /// </summary>
    /// <param name="index">The index of the node to delete.</param>
    private void DeleteAt(int index)
    {
        if (list.Count == 1)
        {
            list.RemoveAt(0);
            return;
        }
        if (index == list.Count - 1)
        {
            list.RemoveAt(list.Count - 1);
            return;
        }
        Swap(index, list.Count - 1);
        list.RemoveAt(list.Count - 1);
        var parentIndex = GetParentIndex(index);
        if (index != 0 && list[index].CompareTo(list[parentIndex]) < 0)
        {
            SiftUp(index);
        }
        else
        {
            Heapify(index);
        } 
    }
        
    /// <summary>
    /// Recursively moves a node up the heap if it is less than its parent.
    /// </summary>
    /// <param name="index">The index of the node.</param>
    private void SiftUp(int index)
    {
        var parentIndex = GetParentIndex(index);
        while (parentIndex != _invalidIndex && list[index].CompareTo(list[parentIndex]) < 0) 
        {
            Swap(index, parentIndex);
            index = parentIndex;
            parentIndex = GetParentIndex(index);
        }
    }

    /// <summary>
    /// Joins another heap to this heap.
    /// </summary>
    /// <param name="other">The other heap.</param>
    public void Union(IPriorityQueue<TKey, TValue> other)
    {
        var casted = (BinaryHeap<TKey, TValue>)other;
        list.AddRange(casted.list);
        BuildHeap();
    }

    /// <summary>
    /// Gets whether the heap is empty.
    /// </summary>
    public bool IsEmpty
    {
        get { return list.Count == 0; }
    }

    /// <summary>
    /// The size of the heap.
    /// </summary>
    public int Size 
    {
        get { return list.Count; }
    }

    /// <summary>
    /// A node object used to store data in the binary heap.
    /// </summary>
    public class Node : INode<TKey, TValue>
    {
        public TKey Key { get; set; }
        public TValue Value { get; set; }

        /// <summary>
        /// Creates a binary heap node initialised with a key.
        /// </summary>
        /// <param name="key">The key to use.</param>
        /// <param name="val">The value to use.</param>
        public Node(TKey key, TValue val) 
        {
            Key = key;
            Value = val;
        }

        public int CompareTo(object other) 
        {
            var casted = other as Node;
            if (casted == null)
                throw new NotImplementedException("Cannot compare to a non-Node object");
            return this.Key.CompareTo(casted.Key);
        }
    }
}
public class BinaryHeap<T extends Comparable<T>> implements HeapInterface<T> {
    /**
     * The heap's data.
     */
    private ArrayList<T> list;

    /**
     * Creates a new {@link BinaryHeap}.
     */
    public BinaryHeap() {
        this(0);
    }

    /**
     * Creates a new {@link BinaryHeap}.
     *
     * @param size The expected maximum size of the heap. this value reduces the number of
     * reallocations to the backing {@link ArrayList}.
     */
    public BinaryHeap(int size) {
        list = new ArrayList<T>(size);
    }

    /**
     * Creates a new {@link BinaryHeap}.
     *
     * @param items An {@link ArrayList} to use as the backing array.
     */
    public BinaryHeap(ArrayList<T> items) {
        list = items;
        buildHeap();
    }

    public void insert(T item) {
        int i = list.size();
        list.add(item);
        int parent = parent(i);
        while (parent != -1 && list.get(i).compareTo(list.get(parent)) < 0) {
            swap(i, parent);
            i = parent;
            parent = parent(i);
        }
    }

    public T extractMin() {
        if (list.size() == 0) {
            return null;
        }
        if (list.size() == 1) {
            return list.remove(0);
        }
        T min = list.get(0);
        T last = list.remove(list.size() - 1);
        list.set(0, last);
        heapify(0);
        return min;
    }

    public T min() {
        if (list.size() == 0) {
            return null;
        }
        return list.get(0);
    }

    public void clear() {
        list.clear();
    }

    public boolean isEmpty() {
        return list.size() == 0;
    }

    public int size() {
        return list.size();
    }

    public void print() {
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + ", ");
        }
        System.out.println();
    }

    private void buildHeap() {
        for (int i = (int)(list.size() / 2); i >= 0; i--) {
            heapify(i);
        }
    }

    private void heapify(int i) {
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l < list.size() && list.get(l).compareTo(list.get(i)) < 0) {
            smallest = l;
        }
        if (r < list.size() && list.get(r).compareTo(list.get(smallest)) < 0) {
            smallest = r;
        }
        if (smallest != i) {
            swap(i, smallest);
            heapify(smallest);
        }
    }

    private void swap(int i1, int i2) {
        T temp = list.get(i1);
        list.set(i1, list.get(i2));
        list.set(i2, temp);
    }

    private int parent(int i) {
        if (i == 0) {
            return -1;
        }
        return (i - 1) / 2;
    }

    private int left(int i) {
        return 2 * i + 1;
    }

    private int right(int i) {
        return 2 * i + 2;
    }

}
'use strict';

/**
 * Creates a binary heap.
 *
 * @constructor
 * @param {function} customCompare An optional custom node comparison
 * function.
 */
var BinaryHeap = function (customCompare) {
  /**
   * The backing data of the heap.
   * @type {Object[]}
   * @private
   */
  this.list = [];

  if (customCompare) {
    this.compare = customCompare;
  }
};

/**
 * Builds a heap with the provided keys and values, this will discard the
 * heap's current data.
 *
 * @param {Array} keys An array of keys.
 * @param {Array} values An array of values. This must be the same size as the
 * key array.
 */
BinaryHeap.prototype.buildHeap = function (keys, values) {
  if (typeof values !== 'undefined' && values.length !== keys.length) {
    throw new Error('Key array must be the same length as value array');
  }

  var nodeArray = [];

  for (var i = 0; i < keys.length; i++) {
    nodeArray.push(new Node(keys[i], values ? values[i] : undefined));
  }

  buildHeapFromNodeArray(this, nodeArray);
};

/**
 * Clears the heap's data, making it an empty heap.
 */
BinaryHeap.prototype.clear = function () {
  this.list.length = 0;
};

/**
 * Extracts and returns the minimum node from the heap.
 *
 * @return {Node} node The heap's minimum node or undefined if the heap is
 * empty.
 */
BinaryHeap.prototype.extractMinimum = function () {
  if (!this.list.length) {
    return undefined;
  }
  if (this.list.length === 1) {
    return this.list.shift();
  }
  var min = this.list[0];
  this.list[0] = this.list.pop();
  heapify(this, 0);
  return min;
};

/**
 * Returns the minimum node from the heap.
 *
 * @return {Node} node The heap's minimum node or undefined if the heap is
 * empty.
 */
BinaryHeap.prototype.findMinimum = function () {
  return this.isEmpty() ? undefined : this.list[0];
};

/**
 * Inserts a new key-value pair into the heap.
 *
 * @param {Object} key The key to insert.
 * @param {Object} value The value to insert.
 * @return {Node} node The inserted node.
 */
BinaryHeap.prototype.insert = function (key, value) {
  var i = this.list.length;
  var node = new Node(key, value);
  this.list.push(node);
  var parent = getParent(i);
  while (typeof parent !== 'undefined' &&
      this.compare(this.list[i], this.list[parent]) < 0) {
    swap(this.list, i, parent);
    i = parent;
    parent = getParent(i);
  }
  return node;
};

/**
 * @return {boolean} Whether the heap is empty.
 */
BinaryHeap.prototype.isEmpty = function () {
  return !this.list.length;
};

/**
 * @return {number} The size of the heap.
 */
BinaryHeap.prototype.size = function () {
  return this.list.length;
};

/**
 * Joins another heap to this one.
 *
 * @param {BinaryHeap} otherHeap The other heap.
 */
BinaryHeap.prototype.union = function (otherHeap) {
  var array = this.list.concat(otherHeap.list);
  buildHeapFromNodeArray(this, array);
};

/**
 * Compares two nodes with each other.
 *
 * @private
 * @param {Object} a The first key to compare.
 * @param {Object} b The second key to compare.
 * @return -1, 0 or 1 if a < b, a == b or a > b respectively.
 */
BinaryHeap.prototype.compare = function (a, b) {
  if (a.key > b.key) {
    return 1;
  }
  if (a.key < b.key) {
    return -1;
  }
  return 0;
};

/**
 * Heapifies a node.
 *
 * @private
 * @param {BinaryHeap} heap The heap containing the node to heapify.
 * @param {number} i The index of the node to heapify.
 */
function heapify(heap, i) {
  var l = getLeft(i);
  var r = getRight(i);
  var smallest = i;
  if (l < heap.list.length &&
      heap.compare(heap.list[l], heap.list[i]) < 0) {
    smallest = l;
  }
  if (r < heap.list.length &&
      heap.compare(heap.list[r], heap.list[smallest]) < 0) {
    smallest = r;
  }
  if (smallest !== i) {
    swap(heap.list, i, smallest);
    heapify(heap, smallest);
  }
}

/**
 * Builds a heap from a node array, this will discard the heap's current data.
 *
 * @private
 * @param {BinaryHeap} heap The heap to override.
 * @param {Node[]} nodeArray The array of nodes for the new heap.
 */
function buildHeapFromNodeArray(heap, nodeArray) {
  heap.list = nodeArray;
  for (var i = Math.floor(heap.list.length / 2); i >= 0; i--) {
    heapify(heap, i);
  }
}

/**
 * Swaps two values in an array.
 *
 * @private
 * @param {Array} array The array to swap on.
 * @param {number} a The index of the first element.
 * @param {number} b The index of the second element.
 */
function swap(array, a, b) {
  var temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

/**
 * Gets the index of a node's parent.
 *
 * @private
 * @param {number} i The index of the node to get the parent of.
 * @return {number} The index of the node's parent.
 */
function getParent(i) {
  if (i === 0) {
    return undefined;
  }
  return Math.floor((i - 1) / 2);
}

/**
 * Gets the index of a node's left child.
 *
 * @private
 * @param {number} i The index of the node to get the left child of.
 * @return {number} The index of the node's left child.
 */
function getLeft(i) {
  return 2 * i + 1;
}

/**
 * Gets the index of a node's right child.
 *
 * @private
 * @param {number} i The index of the node to get the right child of.
 * @return {number} The index of the node's right child.
 */
function getRight(i) {
  return 2 * i + 2;
}

/**
 * Creates a node.
 *
 * @constructor
 * @param {Object} key The key of the new node.
 * @param {Object} value The value of the new node.
 */
function Node(key, value) {
  this.key = key;
  this.value = value;
}

module.exports = BinaryHeap;
# py-data-structures <http://github.com/gwtw/py-data-structures>
# Copyright 2016 Daniel Imms <http://www.growingwiththeweb.com>
# Released under the MIT license <http://github.com/gwtw/py-data-structures/blob/master/LICENSE>

import math
from common.helpers import default_compare

class BinaryHeap:
  def __init__(self, compare=default_compare):
    self.list = []
    self.compare = compare

  def buildHeap(self, keys, values=None):
    if values is not None and len(values) != len(keys):
      raise ValueError('Key array must be the same length as value array')

    nodeArray = []

    for i in range(0, len(keys)):
      nodeArray.append(Node(keys[i], None if values is None else values[i]))

    self.buildHeapFromNodeArray(nodeArray)

  def clear(self):
    self.list = []

  def extractMinimum(self):
    if len(self.list) == 0:
      return None

    if len(self.list) == 1:
      return self.list.pop()

    min = self.list[0]
    self.list[0] = self.list.pop()
    self.heapify(0)
    return min

  def findMinimum(self):
    return None if self.isEmpty() else self.list[0]

  def insert(self, key, value=None):
    i = len(self.list)
    node = Node(key, value)
    self.list.append(node)
    parent = self.getParent(i)
    while parent is not None and self.compare(self.list[i].key, self.list[parent].key) < 0:
      self.swap(self.list, i, parent)
      i = parent
      parent = self.getParent(i)
    return node

  def isEmpty(self):
    return len(self.list) == 0

  def size(self):
    return len(self.list)

  def union(self, otherHeap):
    array = self.list + otherHeap.list
    self.buildHeapFromNodeArray(array)

  def heapify(self, i):
    l = self.getLeft(i)
    r = self.getRight(i)
    smallest = i
    if l < len(self.list) and \
        self.compare(self.list[l].key, self.list[i].key) < 0:
      smallest = l
    if r < len(self.list) and \
        self.compare(self.list[r].key, self.list[smallest].key) < 0:
      smallest = r
    if smallest != i:
      self.swap(self.list, i, smallest)
      self.heapify(smallest)

  def buildHeapFromNodeArray(self, nodeArray):
    self.list = nodeArray
    for i in range(math.floor(len(self.list) / 2), -1, -1):
      self.heapify(i)

  def swap(self, array, a, b):
    temp = array[a]
    array[a] = array[b]
    array[b] = temp

  def getParent(self, i):
    if i == 0:
      return None
    return math.floor((i - 1) / 2)

  def getLeft(self, i):
    return 2 * i + 1

  def getRight(self, i):
    return 2 * i + 2

class Node:
  def __init__(self, key, value):
    self.key = key
    self.value = value

References

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Heapsort” in Introduction to Algorithms, 2nd ed., Cambridge, MA: The MIT Press, 2001, ch. 16, pp.127-144

Comments

comments powered by Disqus
Like this article?
Subscribe for more!