Cancel

多叉堆实现（Rust）

Algorithm

·

November 23, 2022

一个有建立在连续内存上的 $2$ 的 $n$ 次幂倍分叉完全树的最小堆（以下简称 d-ary 堆），理论和实践都最快的，用于图上经典贪心算法，作为斐波那契堆的上位替代。

下图 $q=2^1$

数据结构

/// Min Heap, I is unique, T is weight
#[derive(Clone)]
pub struct DaryHeap<const E: usize, I, T> {
    index: HashMap<I, usize>,
    raw: Vec<(I, T)>,
}

直接使用“索引-权重“二元组来作为节点的结构

基础操作

值得稍微想一想的就是树上父、子位置与索引的换算关系。以下假设我们的叉堆的基是 $2^E$ 。

索引

基本的索引与位置的换算关系靠得是等比数列前 $n$ 项和：

$a_1$ 为首项， $q$ 为比值

\[S_n = \left\{\begin{array}{l} & na_1 &(q=1)\\ &{\large \frac{a_1(1-q^n)}{1-q}} &(q \neq 1)\\ \end{array}\right.\]

对于我们的 d-ary 堆，$a_1 = 1$， $q=2^E$ ，于是有：

\[S_n = \frac{2^{E\cdot n} - 1}{2^E - 1}\]

定义一系列宏来做索引转换的工作

定义基

// 2^E
macro_rules! base {
    () => { 
        {
            1 << E
        } 
    };
}

// (2^E)^n
macro_rules! basen {
    ($n:expr) => { 
        {
            1 << E * ($n)
        } 
    };
}

从编号转换到行列位置

编号和行列位置都从 $1$ 开始，逆转 $S_n$ 公式：

\[2^{En} = S_n(2^E - 1) + 1\]

得出 $n$

\[n = \frac{\log_{2}({S_n(2^E - 1) + 1})}{E}\]

设当前编号为 $N$，行号为 $\text{ln}$ ，列号为 $\text{col}$，则

\[\begin{array}{l} \text{ln} &= \lfloor \frac{\log_{2}({N(2^E - 1) + 1})}{E} \rfloor \\ \text{col} &= N - S_{\text{ln}-1} \end{array}\]

当然这里要采用整数上的数学函数进行运算

macro_rules! pos {
    ($x:expr) => {
        {
            let x = $x;

            // = q^n
            let var = (base!() - 1) * x + 1;

            let mut ln = var.ilog2() as usize / E;
            let mut col: usize = x - total!(ln);

            if col > 0 {
                ln += 1;
            } else {
                col = basen!(ln - 1);
            }

            (ln, col)
        }
    };
}

/// total number for lv complete d-ary
macro_rules! total {
    ($ln:expr) => {
        {
            let ln = $ln;

            debug_assert!(ln > 0);
            debug_assert!(E > 0);

            // 1 * 1-q^n / (1-q)
            (basen!(ln) - 1) / (base!() - 1)
    	}
    };
    ($ln:expr, $col:expr) => {
        {
            let ln = $ln;
            let col = $col;

            debug_assert!(ln > 0);

            if ln == 1 {
                col
            } else {
                total!(ln - 1) + col
            }
    	}
    };
}

当前位置到父母或孩子的位置

macro_rules! paren_pos {
    ($pos:expr) => {
        {
            let (ln, col) = $pos;

            (ln - 1, (col - 1) / base!() + 1)
    	}
    };
}

/// first child pos
macro_rules! child_pos {
    ($pos:expr) => {
        {
            let (ln, col) = $pos;

            (ln + 1, (col - 1) * base!() + 1)
    	}
    };
}

数组下标到父母或孩子下标

最后我们就有了直接的实际数据结构里的索引到它父母或孩子的索引的最终算法

macro_rules! paren {
    ($idx:expr) => {
        {
            let (ln, col) = paren_pos!(pos!($idx + 1));

            total!(ln, col) - 1
    	}
    };
}

macro_rules! child {
    ($idx:expr) => {
        {
            let (ln, col) = child_pos!(pos!($idx + 1));

            total!(ln, col) - 1
    	}
    };
}

交换

交换是 d-ary 堆算法实现依赖的主要操作。

// impl DaryHeap ...     

/// return insert_idx
fn sift_up(&mut self, idx: usize) -> usize {
    let mut cur = idx;

    while cur != 0 {
        let paren = paren!(cur);

        if self.w(cur) < self.w(paren) {
            self.swap(cur, paren);
            cur = paren;
        } else {
            break;
        }
    }

    cur
}

/// return insert_idx
fn sift_down(&mut self, idx: usize) -> usize {
    let mut cur_idx = idx;

    while let Some((child_idx, child_w)) = self.min_child(cur_idx)
    && child_w < &self.raw[cur_idx].1
    {
        self.swap(cur_idx, child_idx);
        cur_idx = child_idx;
    }

    cur_idx
}

fn swap(&mut self, idx1: usize, idx2: usize) {
    if idx1 == idx2 {
        return;
    }

    self.raw.swap(idx1, idx2);

    self.index.insert(self.raw[idx1].0.clone(), idx1);
    self.index.insert(self.raw[idx2].0.clone(), idx2);
}

fn min_child(&self, idx: usize) -> Option<(usize, &T)> {
    let start = child!(idx);
    let end = min(self.len(), start + base!());

    if end <= start {
        return None;
    }

    self.raw[start..end]
    .iter()
    .enumerate()
    .min_by_key(|(_, (_, w))| w)
    .map(|(i, (_, w))| (start + i, w))
}

// ...
  1. 当插入新节点的时候，把新节点放到尾部，然后和父节点比较，如果堆的性质发生违背，就交换两个节点，递归地进行直到到达根节点；
  2. 当更新已有节点的时候，如果新值比旧值大，就向下交换，如果比旧值小，就向上交换，相等就什么都不做；
  3. 删除根节点的时候，把它和序列上最后一个节点交换，然后把最后一个节点向下交换

API 实现

Insert

// impl DaryHeap ...  

/// ReplaceOrPush
pub fn insert(&mut self, i: I, v: T) -> Option<T> {
    if let Some(idx) = self.index.remove(&i) {
        let (_, oldv) = replace(&mut self.raw[idx], (i.clone(), v));

        let newidx = match self.w(idx).cmp(&oldv) {
            Less => self.sift_up(idx),
            Equal => idx,
            Greater => self.sift_down(idx),
        };

        self.index.insert(i, newidx);

        Some(oldv)
    } else {
        self.push(i, v);
        None
    }
}
// ...

DecreaseKey

// impl DaryHeap ...

pub fn decrease_key(&mut self, i: I, v: T) -> Option<T> {
    #[cfg(debug_assertions)]
    {
        if let Some(oldv) = self.get(&i) {
            assert!(&v < oldv);
        }
    }

    self.update(i, v)
}

fn push(&mut self, i: I, v: T) {
    self.raw.push((i.clone(), v));
    self.index.insert(i, self.len() - 1);

    self.sift_up(self.len() - 1);
}

// ...

Pop

pub fn pop(&mut self) -> Option<T> {
    self.pop_item().map(|x| x.1)
}

/// remain None, update self.len
pub fn pop_item(&mut self) -> Option<(I, T)> {
    if self.len() == 0 {
        return None;
    }

    self.swap(0, self.raw.len() - 1);

    let (i, v) = self.raw.pop().unwrap();

    self.sift_down(0);

    Some((i, v))
}

时间复杂度

d-ary 堆本质上当然仍是二叉堆，但当基数较大的时候，实际上原来 $\text{log} n$ 的操作就降低为常量。

insert: $O(1)$

decrease-key: $O(1)$

delete-min (pop): $O(1) $

比较优势

一方面， 尽管 Fib 堆也有类似的时间复杂度，但实现上 Dary 堆是一整块连续的内存，而 Fib 堆是经典的链表结构，因此Dary 堆的实际性能比 Fib 堆好一个数量级；

另一个方面，Rust 标准库里 Binary 堆的实现虽然也建立在连续内存上，但时间复杂度上是 $O(\log n)$ 而不是 $O(1)$ ，在处理较大大规模数据时与 Dary 堆有明显的差距（但基本是同级别的性能表现）

完整代码

经验上，根据处理数据的规模大小，E 可以选择 $2\dots 5$。

© minghu6

·

theme

Simplex theme logo

by golas