A violation heap is a Fibonacci-like heap structure. It has the same amortized bounds for all operations as a Fibonacci heap. The structure has a few differences that help to make it simpler. The first difference is Violation heaps node do not maintain a pointer to their parents. Secondly Violation heaps only need to maintain one int for the rank, unlike Fibonacci heaps which need to maintain two ints, one for number of children and another for if it is colored or not. Finally it does not propagate the removal of the smaller children sub-trees since their loss doesn't affect the number of children greatly especially since the removed node's child with the largest rank (to be defined shortly) is placed in its location.
Structure of the each node in the heap consists of three pointers (left, right, child), an int (rank), and the data that is to be stored. These elements are used as followed:
The root list is a singly linked list (in green) with the other pointer on the same level pointing to NULL (this signifies that you have reached the root). The children are linked with a doubly linked list which would result in the left pointer on the left end and the right pointer on the right end being unused (set to NULL). Use the left pointer that would be set to NULL and instead set it to the parent(in red). Define this node as the "last" node. Each parent-child pointer points to the last node (in blue). Finally the rank which is defined as the ceiling of sum of the rank of its active children over two plus one i.e ceil((r1+r2)/2)+1. (nonexistent children have a rank of -1) where the active children are the last two children of a parent(in yellow).
Operations:
h,h1,h2 are pointer to violation heaps. x is a pointer to violation heap node. v is a value.
Find_min(h) O(1): Reports the minimum of the heap trivial as the violation heap maintains a poin ter to min.
Insert (v,h) O(1): Create new node with value v. Insert this node into the root list of h with rank set to 0. Update the min pointer if necessary.
Before
After:
Meld(h1,h2) O(1): Merge the two root list and set the min to the smaller min between the two heaps like Fibonacci heaps.
Before:
After
Decrease key(v,x,h) O(1): Set the data in the node pointed to by x to v. then: 1. If x is in the root list update the min pointer and then stop. 2. If x is an active node whose new value is still larger than the parent stop. 3. Otherwise remove and glue the active child with larger rank into its place. Insert x into the root list and recalculate the rank of x. Then propagate the rank update upwards as long as the node visited is both a) active and b) has its rank smaller.
case 1 before:
case 1 after:
case 2 before:
case 2 after:
case 3 before:
case 3 after cut:
however the rank 1 of the node with value 12 is wrong. case 3 after:
extract min(h) O(log(n)): Remove the min, merge its children into the root node. Then combine sets of three nodes with the same rank until no such sets exist. This combining step is done by making the smallest valued node the parent and the other two the first and second active children in the children list. Then make the third child the node with larger rank of the formerly active children of the parent and then increment the rank of the parent. This process is called a three-way join.
The triangle represent completely full sub heaps
delete min before:
delete min after: assume the minimum value in c is less than one (if it isn't it can have the min pointer point to it.
three-way combine: created an array large enough to hold two of each rank that can exist in the heap or around 2*log(n)
starting at the min walk along making each element of the array point to the root of a tree.
the third rank 2 tree root has no place to go so we need to initiate a 3-way-combine. first we find which one of the the three will be the new parent (the one with value 1). Then check to see if its first active child has rank smaller than its second active child. if this case it does so the two are swapped
Then they are combined by making the other rank 2 trees the first and second active child of the third rank 2 node.