Binary heap representation

Binary heap representation

rethink about sorting

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.

a heap-ordered complete binary tree

heap representation in array

In a binary heap, the parent of the node in position kk is in position k/2k/2 and, conversely, the two children of the node in positions 2k2k and 2k+12k + 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 kk to k/2k/2; to move down the tree we set kk to 2×k2 \times k or 2×k+12 \times k + 1.

The height of a complete binary tree of size NN is lgN\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 kk in a heap is at position k/2k/2.

bottom-up reheapify

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.

insert into heap

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.

top-down reheapify

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.

remove the maximum from heap

THE END
Ads by Google

林宏

Frank Lin, PhD

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

Using Liquid in Jekyll - Live with Demos

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.

Setup an IKEv2 server with strongSwan

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 two points. In IKEv2 implementations, IPSec provides encryption for the network traffic. IKEv2 is natively supported on some platforms (OS X 10.11+, iOS 9.1+, and Windows 10) with no additional applications necessary, and it handles client hiccups quite smoothly.

Practising closures in JavaScript

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?

Ads by Google