Overview
A skew heap is a heap-ordered binary tree with no explicit balance metadata. Its meld operation recursively merges right paths and swaps children, giving good amortized behavior through self-adjustment.
CoreSource checked
Skew Heap
Maintains a self-adjusting mergeable heap by swapping children during every meld.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Priority Queues
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
meldable priority queuepriority queueslocal searchheap orderdata structures
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(n)
Space
O(n)
When to Use
- Use when a compact meldable heap implementation is more important than worst-case per-operation bounds.
- Use when avoiding rank or null-path metadata is valuable.
When Not to Use
- Avoid when strict worst-case operation bounds are required.
- Avoid when recursion depth or pointer allocation overhead is a concern.
What It Does
- Stores items in a heap-ordered binary tree
- Melds by recursively combining subheaps
- Swaps children on each merge step for self-adjustment
Use Cases
- Simple mergeable priority queues
- Amortized heap operations without balance fields
- Teaching self-adjusting data structures
Inputs
- Keys, values, items, or graph records
- Operations such as insert, delete, or query
Outputs
- Stored structure state
- Query result or updated collection
Pseudocode
- 1.If either heap is empty, return the other heap
- 2.Make the smaller root the new root
- 3.Merge the other heap with the new root's right child
- 4.Swap the new root's left and right children
- 5.Return the new root
Canonical Example
- Input
- meld heaps rooted at 1 and 4
- Output
- heap rooted at 1 after recursive merge and child swap
- Explanation
- The smaller root is kept and subtrees are swapped as part of the self-adjusting meld.
Implementation Notes
- Make meld the primitive for insert and delete-min.
- Document whether meld consumes its input heaps.
- Test repeated increasing and decreasing insert sequences.
Common Pitfalls
- Skipping the child swap removes the self-adjusting behavior.
- Assuming each operation is worst-case logarithmic can be wrong.
- Pointer ownership bugs are common when merging destructively.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow self-adjusting heap merges by swapping children along the merge path on a small meldable priority queue example.
Step 1 of 5: If either heap is empty, return the other heap
data-structures-mechanismNotes
Skew heaps are simple but should be described with amortized, not strict per-operation, guarantees.
Sources (1)
What each reference supports for this entry.
Handbook of Data Structures and Applications
BookData-structures reference for Skew Heap self-adjusting meldable heap operations.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toLeftist Heap
Skew heaps avoid leftist null-path metadata by self-adjusting during meld.
Alternative toPairing Heap
Both are pointer-based heaps with simple meld operations.
Variant ofHeap
A skew heap is a self-adjusting priority queue.
Related Algorithms
Tags
Data StructurePriority Queue