A skew heap (or self-adjusting heap) is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with binary heaps, there are no structural constraints, so there is no guarantee that the height of the tree is logarithmic. Only two conditions must be satisfied:
- The general heap order must be enforced
- Every operation (add, remove_min, merge) on two skew heaps must be done using a special skew heap merge.
A skew heap is a self-adjusting form of a leftist heap which attempts to maintain balance by unconditionally swapping all nodes in the merge path when merging two heaps. (The merge operation is also used when adding and removing values.)
With no structural constraints, it may seem that a skew heap would be horribly inefficient. However, amortized complexity analysis can be used to demonstrate that all operations on a skew heap can be done in O(log n).
Read more about Skew Heap: Definition, References
Famous quotes containing the word heap:
“Self-expression is not enough; experiment is not enough; the recording of special moments or cases is not enough. All of the arts have broken faith or lost connection with their origin and function. They have ceased to be concerned with the legitimate and permanent material of art.”
—Jane Heap (c. 1880–1964)