# Binary heap representation

2020.02.10

The binary heap is a data structure, in which the keys are store in an array such that each key is guaranteed to be larger than (or equal to) the keys at two other specific positions. In turn, each of those keys must be larger than (or equal to) two additional keys, and so forth (heap-ordered). This ordering is easy to see if we view the keys as being in a binary tree structure with edges from each key to the two keys known to be smaller.

The largest key in a heap-ordered binary tree is found at the root.

## Binary heap representation

We draw such a structure by placing the root node and then proceeding down the page and from left to right, drawing and connecting two nodes beneath each node on the previous level until we have draw N nodes. Complete trees provide the opportunity to user a compact array representation that does not involve explicit links. Specifically, we represent complete binary trees sequentially within an array by putting the nodes in level order, with the root at position 1, its children at positions 2 and 3, their children in positions 4, 5, 6, and 7, and so on.

In a binary heap, the parent of the node in position $k$ is in position $k/2$ and, conversely, the two children of the node in positions $2k$ and $2k + 1$. Instead of using explicit links, we can travel up and down by doing simple arithmetic on array indices: to move up the tree from a[k] we set $k$ to $k/2$; to move down the tree we set $k$ to $2 \times k$ or $2 \times k + 1$.

The height of a complete binary tree of size $N$ is $\lg{N}$.

## Reheapify

### Bottom-up reheapify (swim)

If the heap order is violated because a node’s key becomes larger than that node’s parent’s key, then we can make progress toward fixing the violation by exchanging the node with its parent. After the exchange, the node is larger than both its children, but the node may still be larger than its parent. We can fix that violation in the same way, and so forth, moving up the heap until we reach a node with a larger key, or the root node. Coding this process is straightforward when you keep in mind that the parent of the node at position $k$ in a heap is at position $k/2$.

Insert: we add the new key at the end of the array, increment the size of the binary heap, and then swim up through the heap with that key to restore the heap condition.

### Top-down reheapify (sink)

If the heap order is violated because a node’s key becomes smaller than one or both of that node’s children’s keys, then we can make progress toward fixing the violation by exchanging the node with the larger of its two children. This switch may cause a violation at the child; we fix that violation in the same way, and so forth, moving down the heap until we reach a node with both children smaller (or equal), or the bottom.

Remove the maximum: we take the largest key off the top (root), put the item form the end of the binary heap at the top, decrement the size of the heap, and then sink down through the heap with that key to restore the heap condition.

THE END

## 林宏

Frank Lin

Hey, there! This is Frank Lin (@flinhong), one of the 1.41 billion . This 'inDev. Journal' site holds the exploration of my quirky thoughts and random adventures through life. Hope you enjoy reading and perusing my posts.

## YOU MAY ALSO LIKE

Web Notes

2016.08.20

### Using Liquid in Jekyll - Live with Demos

Liquid is a simple template language that Jekyll uses to process pages for your site. With Liquid you can output complex contents without additional plugins.

Tutorials

2020.01.09

### Setup an IKEv2 server with strongSwan

IKEv2, or Internet Key Exchange v2, is a protocol that allows for direct IPSec tunnelling between networks. It is developed by Microsoft and Cisco (primarily) for mobile users, and introduced as an updated version of IKEv1 in 2005. The IKEv2 MOBIKE (Mobility and Multihoming) protocol allows the client to main secure connection despite network switches, such as when leaving a WiFi area for a mobile data area. IKEv2 works on most platforms, and natively supported on some platforms (OS X 10.11+, iOS 9.1+, and Windows 10) with no additional applications necessary.

JavaScript Notes

2018.12.17

### Practising closures in JavaScript

JavaScript is a very function-oriented language. As we know, functions are first class objects and can be easily assigned to variables, passed as arguments, returned from another function invocation, or stored into data structures. A function can access variable outside of it. But what happens when an outer variable changes? Does a function get the most recent value or the one that existed when the function was created? Also, what happens when a function invoked in another place - does it get access to the outer variables of the new place?