Binary Heap Optimisation

Binary Heap Optimisation

Insertion

A binary heap splits nodes into two branches exponentially. It sorts nodes from lowest to highest movement cost so that the lowest number in the group is always the first element in the array. In order to insert an object into the heap it is first placed at the end of the heap as shown as the blank circle in the diagram:

The value is then compared to it's parent (in this case, the 6); if the value is higher than 6 it is in the correct position, if it is less than 6 then the two values swap position. This continues until the value is in the correct position.

How the code sorts up the list:

Extraction

In order to extract from the heap, we remove the top element and replace it with the bottom element (Remove 2 and move 14). Then we check 14 against each of it's children (3 and 6) and swap accordingly with the lowest value child to move the lowest value to the top of the heap.

How the code sorts down the list:

Why the binary heap is useful

Inserted nodes now only have to check against a maximum of 2 other values in the case of the diagram, whereas normally the code would cycle through each node in the array until the lowest value is found.

Extracted nodes may be a bigger optimisation as instead of moving the entire array of nodes by one value if the first node is removed (which takes up a lot of computing power), the first value is removed, replaced and then the replaced node only needs to check four other nodes in the case of the diagram.