Lecture 4: Leftist Heaps and Skew Heaps

zcyzzz cy
  2024-11-13 19:58:07 2024-11-13 19:58:07 Created   2024-11-13 20:05:27 2024-11-13 20:05:27 Updated      98 Words  1 Mins  

Leftist Heaps

Skew Heaps

Amortized Analysis

New Definition

Heavy Nodes and Light nodes: A node p is heavy if , otherwise a light node.

Properties

  1. 当以某个heavy node为根的子树与其他结点合并，那么heavy node一定转变为light node.
  2. 当以某个light node为根的子树与其他结点合并，那么light node可能转变为heavy node.
  3. 在合并的过程中发生heavy/light转换的一定是right path上的结点.
  • Title: Lecture 4: Leftist Heaps and Skew Heaps
  • Author: zcyzzz
  • Created at : 2024-11-13 19:58:07
  • Updated at : 2024-11-13 20:05:27
  • Link: https://rockissleeping.github.io/2024/11/13/ads_lec4/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
Lecture 4: Leftist Heaps and Skew Heaps
  1. 1. Leftist Heaps
  2. 2. Skew Heaps
    1. 2.1. Amortized Analysis
      1. 2.1.1. New Definition
      2. 2.1.2. Properties