Heap Data Structure.

Heap is a data structure, that has uses in sorting and in priority queues.

For more details of algorithms & data structures (they form programs after all) please see literature [4], perhaps more.

Heap is a data structure that can be considered as a full binary tree. It can be implemented in a table (array). Tree is full at every level, perhaps excluding lowest (leaves).

Having a tree node indexed by variable i, we can find parent's position in a table, or/and sons (LEFT, RIGHT):

PARENT(i) = i/2 (round down).
LEFT(i) = (2*i).
RIGHT(i) = (2*i)+1.

On most computers these calculations are fast, using bitwise shift operators.

Heaps also have a property called 'heap property' which means that every (and any) node's value is not greater than parent node's value (at every level).

A[PARENT(i)] >= A[i].

We define node's height as amount of edges (connections), on longest simple line between this node and leaf.

We define tree's height as root's height (tree's root is highest tree node).

No comments:

Post a Comment