ヒープ

二分ヒープ

蟻本p.69

Wikipedia

二分木のうち、以下の制約を満たすものを「二分ヒープ」と呼ぶ。

• 親は子より小さいか等しい

• 子ノードの追加は左から右に向かって行われる

二分ヒープでは次の操作を実現できる。

また、優先度付きキューとしても利用できる。(ただし、優先度変更の操作はない)

• 挿入: \(\mathcal{O}(\log(N))\)

• 最小値の参照: \(\mathcal{O}(1)\)

• 最小値の削除: \(\mathcal{O}(\log(N))\)

Pythonではheapqを使えばよい。

import heapq

h = []
heapq.heappush(h, (5, 'write code'))
heapq.heappush(h, (7, 'release product'))
heapq.heappush(h, (1, 'write spec'))
heapq.heappush(h, (3, 'create tests'))
for i in range(4):
    print(heapq.heappop(h))

(1, 'write spec')
(3, 'create tests')
(5, 'write code')
(7, 'release product')

実装

可変長配列で実装可能。

添え字を1-indexedとすれば、ノード\(i\)の親子ノードは

• 親: \(i/2\)

• 子: \(2i, 2i+1\)

と表すことができる。0-indexedでは次のように置き換えればよい。

• 親: \((i-1)/2\)

• 子: \(2i+1, 2i+2\)

0-indexedでの実装例を示す。

def heappush(h, x):
    h.append(x)
    i = len(h) - 1
    p = (i-1) >> 1
    while i > 0 and h[p] > h[i]:
        temp = h[i]
        h[i] = h[p]
        h[p] = temp
        i = p
        p = (p-1) >> 1

def heapseek(h):
    return h[0]

def heappop(h):
    x = h[0]
    y = h.pop()
    if len(h) == 0:
        return x
    h[0] = y
    i = 0b0
    while i < len(h):
        l = (i<<1) + 1
        r = (i<<1) + 2
        c = i
        if r < len(h) and h[c] > h[r]:
            c = r
        if l < len(h) and h[c] > h[l]:
            c = l
        if c == i:
            return x
        temp = h[i]
        h[i] = h[c]
        h[c] = temp
        i = c
    return x

h = []
heappush(h, 3)
heappush(h, 5)
heappush(h, 2)
heappush(h, 7)
heappush(h, 6)
print(heapseek(h))
print([heappop(h) for i in range(5)])

2
[2, 3, 5, 6, 7]

ヒープソート

Wikipedia

全ての要素をヒープ木に詰めてから順に取り出すことで、ソート済みの配列を得られる。

import heapq

def heapsort(a):
    h = []
    for x in a:
        heapq.heappush(h, x)
    for i in range(len(a)):
        a[i] = heapq.heappop(h)

a = [5, 1, 3, 9, 6, -4, 2, -7, 0]
heapsort(a)
print(a)

[-7, -4, 0, 1, 2, 3, 5, 6, 9]

最小値ではなく最大値を返すヒープ木を使うと、in-placeなソートが可能。

def heapsort(a):

    def push(h, x, hsize):
        h[hsize] = x
        i = hsize
        p = (i-1) >> 1
        while i > 0 and h[p] < h[i]:
            temp = h[i]
            h[i] = h[p]
            h[p] = temp
            i = p
            p = (p-1) >> 1

    def pop(h, hsize):
        x = h[0]
        y = h[hsize - 1]
        if hsize == 1:
            return x
        h[0] = y
        i = 0b0
        while i < hsize:
            l = (i<<1) + 1
            r = (i<<1) + 2
            c = i
            if r < hsize and h[c] < h[r]:
                c = r
            if l < hsize and h[c] < h[l]:
                c = l
            if c == i:
                return x
            temp = h[i]
            h[i] = h[c]
            h[c] = temp
            i = c
        return x

    asize = len(a)
    for i in range(asize):
        push(a, a[i], i)
    for i in range(asize-1, -1, -1):
        a[i] = pop(a, i+1)

a = [5, 1, 3, 9, 6, -4, 2, -7, 0]
heapsort(a)
print(a)

[-7, -4, 0, 1, 2, 3, 5, 6, 9]