Skew Heap Visualization

Self-adjusting binary heap that unconditionally swaps children during merge. Simpler than leftist heaps with comparable amortized performance!

Self-Adjusting Structure

Unconditional Swapping

Skew Heap Visualization

Speed:

🌳

Empty Skew Heap

Nodes

Height

Swaps

Current Step:

Select an operation to begin visualization

Complexity Analysis

O(log n)*

Insert

O(log n)*

Extract Min

O(1)

Find Min

O(log n)* Merge

Efficient heap union

*Amortized time complexity

Skew Heap Properties

• Self-Adjusting: Structure changes with each operation

• Unconditional Swap: Always swap left/right during merge

• No Invariants: No null path length or rank to maintain

• Min-Heap Property: Parent ≤ both children

• Simpler: Easier to implement than leftist heaps

• Amortized Efficiency: O(log n) for merge operations

The Skewing Process

Step 1: Compare roots, keep smaller as new root

Step 2: Recursively merge larger root with right subtree

Step 3: SWAP left and right children (always!)

Key Insight: The unconditional swapping balances the tree over time, ensuring amortized O(log n) performance without maintaining explicit balance information.

vs Leftist Heaps

Simpler: No null path length to maintain

Less Memory: No extra data per node

Unconditional: Always swap, no comparisons needed

Amortized: Same O(log n) complexity but amortized

Applications

• Simple Priority Queues: When simplicity matters more than worst-case

• Educational: Teaching heap concepts without complexity

• Mergeable Heaps: When frequent merging is needed

• Functional Programming: Easier to implement functionally

Implementation

class SkewHeapNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class SkewHeap:
    def __init__(self):
        self.root = None
    
    def merge(self, h1, h2):
        """
        Merge two skew heaps - O(log n) amortized
        Key: Always swap left and right children after merge
        """
        # Base cases
        if h1 is None:
            return h2
        if h2 is None:
            return h1
        
        # Ensure h1 has smaller root (min-heap property)
        if h1.value > h2.value:
            h1, h2 = h2, h1
        
        # Recursively merge h2 with right subtree of h1
        h1.right = self.merge(h2, h1.right)
        
        # SKEW: Always swap left and right children
        # This is what makes it "skew" and self-adjusting!
        h1.left, h1.right = h1.right, h1.left
        
        return h1
    
    def insert(self, value):
        """Insert a value - O(log n) amortized"""
        new_node = SkewHeapNode(value)
        self.root = self.merge(self.root, new_node)
    
    def extract_min(self):
        """Remove and return minimum - O(log n) amortized"""
        if self.root is None:
            return None
        
        # Save minimum value
        min_value = self.root.value
        
        # Merge left and right subtrees
        self.root = self.merge(self.root.left, self.root.right)
        
        return min_value
    
    def find_min(self):
        """Find minimum value - O(1)"""
        return self.root.value if self.root else None
    
    def is_empty(self):
        return self.root is None
    
    def merge_with(self, other_heap):
        """Merge with another skew heap - O(log n) amortized"""
        self.root = self.merge(self.root, other_heap.root)
        other_heap.root = None  # Other heap becomes empty

# Example usage demonstrating the simplicity
heap = SkewHeap()

# Insert elements
for value in [15, 10, 20, 8, 25]:
    heap.insert(value)

# Extract minimum
min_val = heap.extract_min()  # Returns 8

# Merge two heaps
heap2 = SkewHeap()
heap2.insert(5)
heap2.insert(12)
heap.merge_with(heap2)  # Combine heaps

Skew Heap Properties

• Self-Adjusting: Structure changes with each operation

• Unconditional Swap: Always swap left/right during merge

• No Invariants: No null path length or rank to maintain

• Min-Heap Property: Parent ≤ both children

• Simpler: Easier to implement than leftist heaps

• Amortized Efficiency: O(log n) for merge operations

The Skewing Process

Step 1: Compare roots, keep smaller as new root

Step 2: Recursively merge larger root with right subtree

Step 3: SWAP left and right children (always!)

Key Insight: The unconditional swapping balances the tree over time, ensuring amortized O(log n) performance without maintaining explicit balance information.

Implementation

class SkewHeapNode: def __init__(self, value): self.value = value self.left = None self.right = None class SkewHeap: def __init__(self): self.root = None def merge(self, h1, h2): """ Merge two skew heaps - O(log n) amortized Key: Always swap left and right children after merge """ # Base cases if h1 is None: return h2 if h2 is None: return h1 # Ensure h1 has smaller root (min-heap property) if h1.value > h2.value: h1, h2 = h2, h1 # Recursively merge h2 with right subtree of h1 h1.right = self.merge(h2, h1.right) # SKEW: Always swap left and right children # This is what makes it "skew" and self-adjusting! h1.left, h1.right = h1.right, h1.left return h1 def insert(self, value): """Insert a value - O(log n) amortized""" new_node = SkewHeapNode(value) self.root = self.merge(self.root, new_node) def extract_min(self): """Remove and return minimum - O(log n) amortized""" if self.root is None: return None # Save minimum value min_value = self.root.value # Merge left and right subtrees self.root = self.merge(self.root.left, self.root.right) return min_value def find_min(self): """Find minimum value - O(1)""" return self.root.value if self.root else None def is_empty(self): return self.root is None def merge_with(self, other_heap): """Merge with another skew heap - O(log n) amortized""" self.root = self.merge(self.root, other_heap.root) other_heap.root = None # Other heap becomes empty # Example usage demonstrating the simplicity heap = SkewHeap() # Insert elements for value in [15, 10, 20, 8, 25]: heap.insert(value) # Extract minimum min_val = heap.extract_min() # Returns 8 # Merge two heaps heap2 = SkewHeap() heap2.insert(5) heap2.insert(12) heap.merge_with(heap2) # Combine heaps

Skew Heap Visualization