今回は、ヒープ(上方移動・下方移動)のアルゴリズムを Python3 で実装してみました。

0. 前提条件

  • LMDE 2 (Linux Mint Debian Edition 2; 64bit) での作業を想定。
  • Python 3.6.4 での作業を想定。
  • 当方は他のバージョンとの共存環境であり、 python3.6, pip3.6 で 3.6 系を使用するようにしている。(適宜、置き換えて考えること)

1. アルゴリズムについて

当ブログ過去記事を参照。

2. Python スクリプトの作成

  • 敢えてオブジェクト指向で作成している。
  • Shebang ストリング(1行目)では、フルパスでコマンド指定している。(当方の慣習
  • 数値計算ライブラリ NumPy は使用しない。(この程度の行列計算は List で充分)
  • 必要であれば、スクリプト内の定数を変更する。
heap_upward.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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#! /usr/local/bin/python3.6
"""
Heap generation with the upward method
"""
import random
import sys
import traceback


class Heap:
    N = 100  # Number of data

    def __init__(self):
        self.base = []
        for _ in range(self.N):
            self.base.append(random.randrange(self.N) + 1)
        self.__display(0)
        self.heap = [0 for _ in range(self.N + 1)]

    def generate(self):
        """ Heap generation """
        try:
            for n in range(1, self.N + 1):
                self.heap[n] = self.base[n - 1]
                s = n
                p = int(s / 2)
                while s >= 2 and self.heap[p] > self.heap[s]:
                    w = self.heap[p]
                    self.heap[p] = self.heap[s]
                    self.heap[s] = w
                    s = p
                    p = int(s / 2)
            self.__display(1)
        except Exception as e:
            raise

    def __display(self, k):
        """ Display

        :param int k: 0: list of base,
                      1: list of heap
        """
        try:
            print("#### ", end="")
            if k == 0:
                print("Base")
            else:
                print("Heap")
            for i in range(k, self.N + k):
                if k == 0:
                    print("{:5d} ".format(self.base[i]), end="")
                else:
                    print("{:5d} ".format(self.heap[i]), end="")
                if (i + 1 - k) % 10 == 0 or i == self.N - 1 + k:
                    print()
        except Exception as e:
            raise


if __name__ == '__main__':
    try:
        obj = Heap()
        obj.generate()
    except Exception as e:
        traceback.print_exc()
        sys.exit(1)
heap_downward.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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#! /usr/local/bin/python3.6
"""
Heap generation with the downward method
"""
import random
import sys


class Heap:
    N = 100  # Number of data

    def __init__(self):
        self.heap = [0]
        for _ in range(self.N):
            self.heap.append(random.randrange(self.N) + 1)
        self.__display(0)

    def generate(self):
        """ Heap generation """
        try:
            n = self.N
            for i in range(int(n / 2), 0, -1):
                p = i
                s = 2 * p
                while s <= n:
                    if s < n and self.heap[s + 1] < self.heap[s]:
                        s += 1
                    if self.heap[p] <= self.heap[s]:
                        break
                    self.__swap(p, s)
                    p = s
                    s = 2 * p
            self.__display(1)
        except Exception as e:
            raise

    def __swap(self, a, b):
        """ Swapping

        :param int a: index of heap list
        :param int b: index of heap list
        """
        try:
            w = self.heap[a]
            self.heap[a] = self.heap[b]
            self.heap[b] = w
        except Exception as e:
            raise

    def __display(self, k):
        """ Display

        :param int k: 0: list of tree,
                      1: list of heap
        """
        try:
            print("#### ", end="")
            if k == 0:
                print("Tree")
            else:
                print("Heap")
            for i in range(1, self.N + 1):
                print("{:5d} ".format(self.heap[i]), end="")
                if i % 10 == 0 or i == self.N:
                    print()
        except Exception as e:
            raise


if __name__ == '__main__':
    try:
        obj = Heap()
        obj.generate()
    except Exception as e:
        print("EXCEPTION!", e.args, file=sys.stderr)
        sys.exit(1)

3. Python スクリプトの実行

まず、実行権限を付与。

1
2
$ chmod +x heap_upward.py
$ chmod +x heap_downward.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
$ ./heap_upward.py
#### Base
   31     6    16    22    45     5    62    78    90    14
   51     7    84    39    46    47    71    12    97    33
   87    66    98    79    47     1    29    51    93    10
   14    41    55    97    14    28    32    40    97    29
   83    76    98    83    58    28    62    96    76    25
   37    40    26    11    88    23    79    15    16    61
   54    34    25     6    65    18    50    96    70    95
   78    34    92    83    56    83    85    37     2    69
   38    84     1    26    75    10    51    60    73    37
   89    50    25    11    48    50    55    26    69    16
#### Heap
    1     1     5     6     2     6    10    14    12    10
   11    16     7    15    14    14    41    31    28    29
   22    37    25    26    16    26    11    51    16    46
   25    47    18    70    71    34    32    83    37    38
   33    75    26    60    58    50    28    55    50    25
   37    84    40    29    88    62    79    93    23    61
   54    39    34    78    65    55    50    97    96    95
   78    90    92    83    56    97    85    97    40    69
   45    84    83    87    76    98    51    83    73    66
   89    98    51    62    48    96    76    79    69    47

$ ./heap_downward.py
#### Tree
   35    89    14    86    95    49    69     3   100    84
   62    98    78    34    19    17    59    77    41    39
  100    27     2    32    43    18    78    91    34    93
   12     8    66    69    11    12    73    63    20    43
   70    29    73    82    56    62    40    56    71    71
   85    25    32    72    13    13    14    90     5    98
   47    64    61     8    89     8    31    74    38    79
   75    65    70    37    12    85    88    58    65    72
   28     9     5    57    40    87    92    29    98    77
   82    20    63    52     1    61    47    96    14    92
#### Heap
    1     2     5     3     5    13    12     8    12     9
   20    14    18    13    14     8    11    12    20    28
   29    27    40    32    43    25    72    14    34    47
   19    17     8    38    59    65    37    63    41    35
   39    40    73    29    56    62    52    47    71    71
   85    49    32    78    78    91    69    90    34    98
   93    64    61    86    89    66    31    74    69    79
   75    77    70   100    73    85    88    58    65    72
   43    84    70    57   100    87    92    82    98    77
   82    95    63    89    62    61    56    96    98    92

以上