コンテンツにスキップ

Week 7 (2025/5/30)

今週の目的

データをヒープに格納し、ヒープの基本的な操作を行う。

今週のキーワード

  • リストによる完全二分木の実装
  • シフトアップ、シフトダウンによるヒープ再構築

今回はヒープソートの準備として、ヒープと呼ばれるデータ構造を実装する。 ヒープとはヒープ条件を満たす完全二分木（必ず２個以下の子を持つ左詰めの木構造） をいう。 ヒープ条件とはある節の値がその子孫のどの節よりも小さいこと である。つまり、どの節も自分の親よりも値が大きいことである。

このヒープの基本操作であるinsert（節の挿入）、delete_min（根の削除）、build_heap（ヒープの構成）の３つを実装する。

課題1：ヒープにデータを挿入する

データをヒープに挿入するinsertメソッドとヒープを表示するshow_treeメソッドを備えたHeapクラスを実装せよ。insertメソッドは、データを格納した新しい節をヒープの最後に挿入し、その後、shift_upメソッドを用いて挿入した節を適切な位置（ヒープ条件を満たす位置）まで押し上げる。

Heapクラスの仕様は、以下の通りである。

Heapクラス

class Heap()
データを格納するヒープのクラス

インスタンス変数

  • list: データ格納用のリスト(リスト)。0番目は使わないのでダミーデータ（e.g. 0など）を格納する。
  • size: ヒープのサイズ（整数）

insert(data)
データをヒープに格納するメソッド

パラメータ

  • data: 格納するデータ（Stopインスタンス）

shift_up(num)
ヒープのnum番目のノードをシフトアップするメソッド

パラメータ

  • num: シフトアップするデータのインデックス（整数）

show_tree()
ヒープの中身を木構造で表示するメソッド

is_heap()
ヒープの中身がヒープ条件を満たしているか確認するメソッド

返り値

  • ヒープ条件を満たしていればTrue、そうでなければFalseを返す（ブール値）

さらに、allkyotobus_stop.datからバス停データを読み込み、読み込んだ順にヒープにデータをinsertし、最後にヒープを表示するよう、以下のプログラムの穴あき部分を埋めて、実行例の通りに動くことを確認せよ。なお、ヒープの各節に割り当てられる値はバス停データの経度とする。

week7_1.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 穴埋め問題用のプログラム
from def_stop import Stop  # Stopクラスの読み込み
import sys  # 再帰呼び出し回数の上限を変更するためのモジュール
sys.setrecursionlimit(10000)  # 再帰呼び出し回数の上限を10,000回に変更


class Heap:  # Heapクラスの定義
    def __init__(self):
        self.list = [0]  # データを格納するリスト。0番目の要素は使わないため0を代入。
        self.size = 0

    def insert(self, data):
        self.list.append(data)  # データをヒープの最後の要素の次に挿入
        self.size += 1  # ヒープサイズを1増やす
        self.shift_up([____])  # 挿入した要素をシフトアップする

    def shift_up(self, num):  # num番目の要素をシフトアップ
        # num番目の要素が根でなく、num番目の要素の親の方が大きい場合、親子を入れ替え
        if num > [____] and self.list[[____]].lng > self.list[num].lng:
            self.list[num], self.list[[____]] = self.list[[____]], self.list[num]
            self.shift_up([____])  # 入れ替え後に、引き続き新しい親のシフトアップ

    def show_tree(self, num):  # num番目の要素を根とする木（もしくは部分木）を表示するメソッド
        if num <= self.size:  # 要素numがヒープサイズの範囲内である限り
            self.show_tree([____])  # 要素numの右子を根とする部分木を表示
            i = num
            space = ''
            while i // 2 > 0:  # 要素numの深さ分だけ半角スペース2個を連結
                space += '  '
                i = i // 2
            print('{}{}:{}'.format(space, self.list[num].name, self.list[num].lng))  # 連結されたタブ（インデント）と要素numのバス停の名前と経度を表示
            self.show_tree([____]) # 要素numの左子を根とする部分木を表示

    def is_heap(self):  # ヒープ条件のチェック
        for i in range(self.size, 1, -1):
            if self.list[i].lng < self.list[i//2].lng:
                return False
        return True


if __name__ == '__main__':  # モジュールとしてインポートされるときは実行しない
    fi = open('allkyotobus_stop.dat', 'r', encoding = 'utf-8')
    lines = fi.readlines()
    heap = Heap()
    for line in lines:
        line = line.rstrip()
        items = line.split(' ')  # 1行を半角スペースで区切ってitemsリストに代入
        # StopインスタンスをHeapインスタンスに挿入
        heap.insert(Stop(items[0], items[1], float(items[2]), float(items[3]), items[4:]))
    if heap.is_heap():
        heap.show_tree([____])  # ヒープ全体を表示
    fi.close()

                                                                中島橋:135.75151985
                                                    大住浜:135.74934167
                                                                竹田駅西口:135.75571764
（中略）
下夜久野駅前:134.99883496
（中略）
                                                                   下三栖:135.75017041
                                                                横大路車庫前:135.74386927
                                                                   出町柳駅前:135.7730189

課題2：最小値を取り出す

課題1で作成したHeapクラスに、最小値を格納した根を削除して取り出すdelete_minメソッド追加せよ。delete_minメソッドでは、根の削除後に根に格納された値を返し、ヒープの最後尾の要素を根に移動させること。ただし、この移動によって木構造がヒープ条件を満たさなくなるため、shift_downメソッドを用いて根を適切な位置（ヒープ条件を満たす位置）まで押し下げる。

Heapクラスのdelete_minメソッドおよびshift_downメソッドの仕様は、以下の通りである。

delete_minメソッドとshift_downメソッド

delete_min()
ヒープの最小値である根を削除するメソッド

返り値

  • ヒープの根に格納されたデータ（Stopインスタンス）

shift_down(num)
ヒープのnum番目のノードをシフトダウンするメソッド

パラメータ

  • num: シフトダウンするデータのインデックス（整数）

さらに、課題1でallkyotobus_stop.datのバス停データから構築したヒープを用いてdelete_minメソッドを３回実行し、最西から３つのバス停が取得できることを確認せよ。

最西のバス停の下夜久野駅前(ID:ED01_85)の緯度経度は(35.32033486, 134.99883496)です。
最西のバス停の畑口(ID:ED01_86)の緯度経度は(35.32009052, 135.00174923)です。
最西のバス停の上梅谷(ID:ED01_3814)の緯度経度は(35.32132338, 135.02203255)です。

課題3：ヒープを作る

課題1で作成したHeapクラスに、与えられたリストからヒープを構築するbuild_heapメソッドを追加せよ。ただし、insertメソッドを繰り返して一つずつデータを追加しヒープを構築した課題１とは違い、与えられたリストからヒープを構成すること。

Heapクラスのbuild_heapメソッドの仕様は、以下の通りである。

build_heapメソッド

build_heap(list)
listを基にヒープを構築するメソッド

パラメータ

  • list: ヒープに格納するデータのリスト（Stopインスタンスのリスト）

ヒント

リストの中央の節が、ヒープの最後尾の節の親であることに着目して、そこからshift_downを用いて部分木をヒープに再構成する。この構成を根まで繰り返し、ボトムアップにヒープを構築するとよい。

さらに、allkyotobus_stop.datから読み込んだバス停データを、読み込んだ順にリストに追加した後、build_heapメソッドでヒープを構築して、ヒープを表示するよう実装せよ。ヒープの構成が課題1と異なるがヒープ条件を満たしていることを確認せよ。

                                                                中島橋:135.75151985
                                                        大住浜:135.74934167
                                                                上賀茂石計町:135.76040489
（中略）
下夜久野駅前:134.99883496
（中略）
                                                                        横大路車庫前:135.74386927
                                                                クレイン京都:135.7194435
                                                                        上賀茂松本町:135.76329587
Back to top