Search on the blog

2010年11月10日水曜日

ヒープを作ってみよう!

今日は、ヒープを自分で実装してみます。
昔、「二分木は配列で実装できます。」みたいなことを読んだことがありました。
そのときは、??だったが、今ならできる!!

では、早速ソースを。



class myHeap {
public:
    myHeap() {
        this->tail = 0;
    }

    void add(int n) {
        hp[tail++] = n;
        int pos = tail-1;
        while (pos) {
            if (hp[(pos-1)/2] < hp[pos])
                swap(hp[(pos-1)/2], hp[pos]);
            pos = (pos-1)/2;
        }
    }

    int pop() {
        if (isEmpty()) {
            cerr << "Heap is empty!" << endl;
            return -1;
        }

        int ret = hp[0];
        hp[0] = hp[--tail];
        int pos = 0;

        while (2 * pos + 2 <= tail) {
            if (hp[pos] > max(hp[2*pos+1], hp[2*pos+2]))
                break;
            if (hp[2*pos+1] > hp[2*pos+2]) {
                swap(hp[pos], hp[2*pos+1]);
                pos = 2*pos+1;
            }
            else {
                swap(hp[pos], hp[2*pos+2]);
                pos = 2*pos+2;
            }
        }
        return ret;
    }

    bool isEmpty() {
        return tail <= 0;
    }

private:
    int hp[1<<10];
    int tail;
};


で、ちゃんと動くか確認してみましょう。


int main() {
    myHeap hp = myHeap();

    REP(i, 100)
        hp.add(rand() % 1000);

    while (!hp.isEmpty())
        printf("%d\n", hp.pop());

    return 0;
}


はい、動きました。
実際に自分で作ってみると、ヒープのオーダーについての理解も深まります。
  • 最大値の参照は、O(1)
  • push()およびpop()は、O(log n)
なのは明らかですね。

0 件のコメント:

コメントを投稿