Knowing Deeper For Deap Tree

DESCRIPTION

Deap is a double-ended heap. Deap can be used to find the smallest and the largest element in heap which is similar with mix-max heap and the algorithms are simpler.

Deap supports several operations :

1. find-min : finding the smallest element

2. find-max : finding the largest element

3. insert : inserting an arbitrary element

4. delete-min : deleting the smallest element

5. delete-max : deleting the largest element

Deap's characteristics :

>> The root contains no element (blank)

>> The left subtree of root is min-heap

>> The right subtree of root is max-heap

>> From it's properties we can conclude that the smallest element is located at the root of min-heap and the largest is located at the root of max-heap

The example of deap tree :

Corresponding Nodes :

Corresponding Nodes can be seen with the color from the picture

Each node in left-subtree has its corresponding node in the right-subtree (in a similar location).If there’s no node at its partner location then it will correspond to its partner parent.

min-partner(x) : min-heap node that corresponds to the max-heap of position x. 

max-partner(x) : max-heap node that corresponds to the min-heap of position x.

INSERTION

:: Insert the new element after the last element of deap

:: Check the corresponding nodes and count the corresponding min/max-partner

:: Do min-uphead or max-uphead depends on where is the new element's location

Example : 

 

DELETION

:: First, store the last element of deap  in T and decreased the number of element in deap

:: Transform the deletion of root of min-heap into deletion of leaf of min-heap by shifting vacancy at the root of the min-heap

:: Compute y = max-parnert(x)

:: If y's value > T, no swap needed and insert T at x's position

:: If y's value < T, swap y's value with T and insert y's value (now T) at x's position

:: Uphead the inserted node

 

The result of deletion