Binary Trees: The Heap.

Binary Trees: The Heap.

David PynesBlockedUnblockFollowFollowingJan 12IntroductionIn 1964, J.

Williams the Welsh-born Canadian, developed a structure to find max values.

This structure is the heap.

The heap is semi-ordered, with the maximum value always at the top.

WhyLet’s say you are in charge of a hospital and there are a number of patients in the waiting room.

As each patient waits for the doctor, the patients form a queue.

Now imagine a patient is rushed in to the hospital in emergency condition.

Should this patient be placed at the end of the queue with the other patients or should the patient be given priority?In computing this concept of priority is similar.

The heap gives priority by having higher values higher up the heap.

WhatThe heap is a binary tree with two additional properties.

The heap is complete.

That means that every branch in the tree has both of it’s children (except for the last level).

The heap is semi-ordered.

That means the higher level nodes are always larger than the lower level nodes, also implying the top node is the maximum.

Heaps are complete, so heaps are often implemented within a contiguous data structure, i.

e.

an array.

Let’s describe connection between the array and binary tree.

Notice in the image above that the first index (of the array) is the root (of the binary tree).

Now notice the arrows of the array mimic the arrows of the binary tree.

The connection here is that a parent and a child in an binary tree can be calculated in an array as index i*2+1 (left) and i*2+2 (right).

This also means that a child’s parent can be calculated at floor(i-1/2).

Okay, now onto maintaining the heap properties.

Up heap occurs when a node is inserted in to the heap.

Up heap occurs because nodes are always added at the most immediate location in the heap, but by doing this the insert does not consider the heap’s semi-ordered property.

Let’s describe up heap with an example.

Look at this newly inserted value seven.

Since the heap is complete, the node starts by being placed as a leaf on the tree, but seven is larger than the higher level node.

This is cause for an up heap.

That is, seven swaps with the three.

On the higher level, the heap checks again for more up heaping.

Looks like seven is also larger than five so, up heap.

Now seven has swapped so high that there is no where else to up heap to.

Up heaping carries on this way until either, the node is at the top of the heap or until all nodes on higher levels are larger than the nodes on lower levels.

Now the down heap.

This occurs when a node is removed from the heap.

Note, heaps always remove the top node.

First the heap swaps the last node in with the top node.

Next the last value in the tree is removed (the former top node).

Now compare this new top node with the nodes on the lower levels.

If the node(s) on the lower level are larger than the node on the higher level, swap with the largest lower level node.

Look, four and five are both larger than three.

This means five swaps with three.

The heap down heaps until order is restored.

In the example, zero is not larger than three, so the down heap is done.

HowNow let’s associate the ideas with the code.

Let’s start simple and outline the heap class.

class Heap {private: int* tree; int max_size, size; //more code//Notice there is a int* tree, a max_size, and a size.

The int* tree is the array, which will be as large as a max_size.

The size is to let the code know the current size of the heap, which will be important when adding and removing nodes.

Now let’s define some auxiliary functions swap, parent, left and right.

void swap(const int& i, const int& j) { const int temp_val = tree[i]; tree[i] = tree[j]; tree[j] = temp_val; }const int parent(const int& child) { return ( (child – 1)/2 ); }const int left_child(const int& parent) { return ( parent*2 + 1 ); } const int right_child(const int& parent) { return ( parent*2 + 2 ); }As described in the previous section, the children are respectively i*2 + 1 or i*2 + 2, the parent is floor((i-1)/2), and swap swaps nodes.

Next let’s write a function to grow the tree.

In other words, what to do when size ≥ max_size.

void grow_tree() { max_size = max_size << 1 | 1; int* prev_tree = tree; tree = new int[max_size]; for(int i=0; i<size; i++) tree[i] = prev_tree[i]; delete[] prev_tree; }A full and complete tree has at most 2^n-1 nodes, Therefor the max_size should always therefor be some 2^n-1.

This line of code does that: max_size = max_size << 1 | 1;This bitwise code translates to, “shift the bits to the left once then add one.

”Anyways, on to insert.

void insert(const int val) { if( size == max_size ) grow_tree(); tree[size] = val; upHeap(size++);}The insert function starts by checking the need to grow, if so then grow.

Next we place the new node as the last entry in the tree, then up heap.

Note, the heap size is increased with the post-increment operator size++.

void upHeap(const int child) { const int root = 0 if( child == root) return; if( tree[child] > tree[parent(child)] ) { swap( child, parent(child) ); upHeap( parent(child) ); }}Up heap is a recursive function.

All recursive functions have a base case.

For up heap the base case is having the node swap to the top (the root).

On the other hand, if the incoming node is not at the top, check if there should be a swap.

If so, swap and repeat on a higher level.

Now onto remove and down heap.

void remove() { const int root = 0; if( size == 0 ) return; swap(root, –size); downHeap(root);}As described in the previous section, start by swapping the top node with the last node in the heap, then proceed to down heap from the top.

Note, the decrement operator, — size, is used to reduce the size of the heap.

void downHeap(const int parent) { if( right_child(parent) >= size ) return; int temp = parent; if( tree[temp] < tree[left_child(parent)] ) temp = left_child(parent); if( tree[temp] < tree[right_child(parent)] ) temp = right_child(parent); if( temp != parent ) { swap( parent, temp ); downHeap(temp); }}Down heap is also a recursive function.

This time the base case is when the down heaping reaches a leaf, i.

e.

there is no further down to go.

Otherwise, down heaping checks and selects the larger of the lower level nodes, swaps and repeats on a lower level.

Now we can put the code together and create the heap data structure.

For the full C++ program follow the instruction below.

Copy the full source code here and save as main.

cppCompile from the command line, g++ main.

cpp -o Heap.

exeThen execute the code from command line, .

/Heap.

exeThe codeView the full C++ code: here.

Create a visual on the web app: here.

.