Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

BinaryHeapのデバグメッセージを信用するなかれ

標準ライブラリのBinaryHeapの罠

競プロで頻出のプライオリティキューですが、少しだけ注意点があります。それは、dbgマクロで表示した時の順番がpop順ではないことです。本当に正しくキューがセットされてるか知るためにデバグメッセージを出しても、そこに書いてあるのはpop順ではないです。

fn main()
{
    let mut q = std::collections::BinaryHeap::new();
    for x in &[3,4,5,1,2,2,7,6] {
        q.push(x);
    }
    dbg!(&q);
    
    while !q.is_empty() {
        dbg!(q.pop().unwrap());
    }
}

pop順は降順ですが、dbgマクロで表示されるものは、降順になってないことがわかります。しかし実際にpopしてみると、降順になります。

[prog.rs:9] &q = [
    7,
    6,
    5,
    3,
    2,
    2,
    4,
    1,
]
[prog.rs:12] q.pop().unwrap() = 7
[prog.rs:12] q.pop().unwrap() = 6
[prog.rs:12] q.pop().unwrap() = 5
[prog.rs:12] q.pop().unwrap() = 4
[prog.rs:12] q.pop().unwrap() = 3
[prog.rs:12] q.pop().unwrap() = 2
[prog.rs:12] q.pop().unwrap() = 2
[prog.rs:12] q.pop().unwrap() = 1

たしかめよう

さて、このデバグメッセージは何に由来してるものなのか調べるために、「たぶん中の配列をまるまる表示してるだけだろう」とあたりをつけて、自分でも二分ヒープを実装してみました。(たぶん実装あってるよね?)

struct BinaryHeap {
    v: Vec<i64>
}
impl BinaryHeap {
    fn new() -> BinaryHeap {
        Self {
            v: vec![]
        }
    }
    fn rebuild(&mut self) {
        for i in (0..self.v.len()/2).rev() {
            self.max_heapify(i);
        }
    }
    fn push(&mut self, x: i64) {
        self.v.push(x);
        self.rebuild()
    }
    fn max_heapify(&mut self, i: usize) {
        let left = 2*i + 1;
        let right = 2*i + 2;
        let mut new_p = i;
        if left < self.v.len() && self.v[i] < self.v[left] {
            new_p = left;
        }
        if right < self.v.len() && self.v[i] < self.v[right] {
            new_p = right;
        }
        if new_p != i {
            self.v.swap(i, new_p);
            self.max_heapify(new_p);
        }
    }
}

同じ要素をプッシュしてみると、

let mut q = BinaryHeap::new();
for x in &[3,4,5,1,2,2,7,6] {
    q.push(*x);
}
dbg!(&q.v)

確かに内部の配列がライブラリのものと同じになりました。

[src/heapify.rs:45] &q.v = [
    7,
    6,
    5,
    3,
    2,
    2,
    4,
    1
]

今回の学び

  • BinaryHeapのデバグメッセージは信用出来ない。これを表示して「あれープライオリティキューが壊れてんのか?」と悩むのは意味ないのでやめましょう
  • 標準ライブラリのBinaryHeapが何をもとにしてデバグメッセージを表示しているか調べるために、二分ヒープを実装して確かめた。その結果、「たぶん、中身の配列をそのまま表示してるだけだろう」という結論に至った