ヒープを作ってみよう！

今日は、ヒープを自分で実装してみます。

昔、「二分木は配列で実装できます。」みたいなことを読んだことがありました。

そのときは、？？だったが、今ならできる！！

では、早速ソースを。

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)

なのは明らかですね。