ヒープを作ってみよう！

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

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

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

では、早速ソースを。

view plainprint?

1. class myHeap {  
2. public:  
3.     myHeap() {  
4.         this->tail = 0;  
5.     }  
6.   
7.     void add(int n) {  
8.         hp[tail++] = n;  
9.         int pos = tail-1;  
10.         while (pos) {  
11.             if (hp[(pos-1)/2] < hp[pos])  
12.                 swap(hp[(pos-1)/2], hp[pos]);  
13.             pos = (pos-1)/2;  
14.         }  
15.     }  
16.   
17.     int pop() {  
18.         if (isEmpty()) {  
19.             cerr << "Heap is empty!" << endl;  
20.             return -1;  
21.         }  
22.   
23.         int ret = hp[0];  
24.         hp[0] = hp[--tail];  
25.         int pos = 0;  
26.   
27.         while (2 * pos + 2 <= tail) {  
28.             if (hp[pos] > max(hp[2*pos+1], hp[2*pos+2]))  
29.                 break;  
30.             if (hp[2*pos+1] > hp[2*pos+2]) {  
31.                 swap(hp[pos], hp[2*pos+1]);  
32.                 pos = 2*pos+1;  
33.             }  
34.             else {  
35.                 swap(hp[pos], hp[2*pos+2]);  
36.                 pos = 2*pos+2;  
37.             }  
38.         }  
39.         return ret;  
40.     }  
41.   
42.     bool isEmpty() {  
43.         return tail <= 0;  
44.     }  
45.   
46. private:  
47.     int hp[1<<10];  
48.     int tail;  
49. };  

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;
};

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

view plainprint?

1. int main() {  
2.     myHeap hp = myHeap();  
3.   
4.     REP(i, 100)  
5.         hp.add(rand() % 1000);  
6.   
7.     while (!hp.isEmpty())  
8.         printf("%d\n", hp.pop());  
9.   
10.     return 0;  
11. }  

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)

なのは明らかですね。