Wednesday, July 24, 2013

What does std::make_heap do?

std::make_heap reorder elements in container to satisfy definition of binary max heap.

Building binary max heap algorithm
Here is algorithm from wiki in pseudo code.
Function Build-Max-Heap calls Max-Heapify which do the main part of job [1].

Max-Heapify (A, i):
 left ← 2i
 right ← 2i + 1
 if leftheap_length[A] and A[left] > A[largest] then:
 if rightheap_length[A] and A[right] > A[largest] then:
 if largesti then:
 swap A[i] ↔ A[largest]  
 Max-Heapify(A, largest)

Build-Max-Heap (A):
 heap_length[A] ← length[A]
 for ifloor(length[A]/2) downto 1 do
 Max-Heapify(A, i)

Implemenation of building binary max heap algorithm in C++
Below is code with implemenation of functions defined in pseudo code above.

Result of code execution is:
9 8 7 4 5 6 3 2 1 
Execution result it is result positions of elements in vector:

Representation of this array as binary heap:

[1]. Binary heap From Wikipedia, the free encyclopedia.

No comments:

Post a Comment