Lably
Skip to content

Skew heap

Binary tree heap data structure

  • 7 min read
  • 2 chapters

Related on Lably

Through Data structure, Binary tree and Recursion

Lab · Class 8–12Algorithms & Sorting
  • 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). In fact, with φ=1+52 denoting the golden ratio, the exact amortized complexity is known to be logφ n (approximately 1.44 log2 n).

Definition

Skew heaps may be described with the following recursive definition:

  • A heap with only one element is a skew heap.
  • The result of skew merging two skew heaps sh1 and sh2 is also a skew heap.

Sign in to keep reading

One more chapter is free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard