In [1]:
1
2
3
4
import random, sys
from binarytree import build
sys.path.append("/home/swyoo/algorithm")
from utils.verbose import logging_time, printProgressBar
Generate array
In [2]:
1
2
3
4
5
nrange = 100
ratio = 0.2
# sizes = list(np.logspace(start=0, stop=7, num=num_exp))
size = 20
a = [random.randint(int(- ratio * nrange), int((1 - ratio) * nrange)) for _ in range(size)]
In [3]:
1
2
3
4
5
6
def plot(a:list):
""" plot `a` as a binary tree """
print(build(a))
print(a)
plot(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
[-6, 4, 58, 26, -18, 6, 60, 63, 45, 28, 26, 6, 73, 4, 79, 46, -18, 76, -9, 11]
_____________-6_______
/ \
__________4_______ ___58__
/ \ / \
_____26___ _-18 6 60
/ \ / \ / \ / \
_63_ _45 _28 26 6 73 4 79
/ \ / \ /
46 -18 76 -9 11
Heap
Max heap properties
- complete binary tree
- parent’s key > child’s key
힙은 완전이진트리(complete binary tree) 성질을 만족하기 때문에 다음처럼 1차원 배열(array)로 표현이 가능.
몇가지 function을 추가하여 prioirity queue로 구현 가능
for loop version
heapify: $T(n) = T(n/2) + 1 = O(logn)$
build_heap: $T(n) = 2T(n/2) + O(n) = O(nlogn)$
하지만, tighter bound 는 \(O(n)\) 이다. geeksforgeeks, pdf에서 증명하였다.
간략하게 설명하면 다음과 같다.
각 level(높이) 에서 노드(원소)의 갯수는 binary tree이고, index를 기반으로 쉽게 생각가능하다.
간략화를 위해 full binary tree의 경우를 생각해보자.
예를들면, level 0에서는 $n/2$ 개, level 1에서는 $n/2 - n/4 = n/4$의 노드가 있다.
따라서, build_heap 함수의 tight time complexity는 다음과 같이 계산 가능하다.
그 level의 모든 노드들이 heapify할때 걸리는 시간은 그 위치의 level * 그 level의 모든 노드 수
따라서, 모든 level의 노드들이 heapify하는데 걸리는 시간을 계산하는 것이다.
\[\begin{align*}
0\cdot \frac { n }{ { 2 }^{ 1 } } &+1\cdot \frac { n }{ { 2 }^{ 2 } } +2\cdot \frac { n }{ { 2 }^{ 3 } } +3\cdot \frac { n }{ { 2 }^{ 4 } } +...\\ &=\frac { n }{ 4 } \cdot \left( 1+2\cdot \frac { 1 }{ 2 } +3\cdot \frac { 1 }{ 4 } +... \right) \\ &=\frac { n }{ 4 } \cdot c=O\left( n \right)
\end{align*}\]
따라서, 모든 level의 노드들이 heapify하는데 걸리는 시간을 계산하는 것이다.
implementation
구현하면서 주의해야할 점은
complete binary tree이므로, base case인 leaf 노드는 왼쪽 child 가 마지막 index를 초과했을 때이다.
또한, 왼쪽 child만 있을 수 있으므로, left, right 에대해 접근할때 허용하는 index 범위 안에 있는지 확인이 필요.
complete binary tree이므로, base case인 leaf 노드는 왼쪽 child 가 마지막 index를 초과했을 때이다.
또한, 왼쪽 child만 있을 수 있으므로, left, right 에대해 접근할때 허용하는 index 범위 안에 있는지 확인이 필요.
In [4]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@logging_time
def build_heap(a):
""" build max heap using for loop. """
def heapify(i):
""" a[i] finds a proper position to satisfy heap-property. """
left, right = 2*i+1, 2*i+2
if left > len(a) - 1: return # base case
indices = [k for k in [left, right, i] if k < len(a)]
largest = max(indices, key=lambda idx: a[idx])
if i != largest:
a[largest], a[i] = a[i], a[largest]
heapify(largest)
for i in range((len(a) // 2) - 1, -1, -1):
heapify(i)
In [5]:
1
2
3
4
a = [random.randint(int(- ratio * nrange), int((1 - ratio) * nrange)) for _ in range(size)]
plot(a)
build_heap(a, verbose=True)
plot(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
______________6________
/ \
_________77_______ ___-1____
/ \ / \
___69___ _10 _38 _2
/ \ / \ / \ / \
_-3 _69 _39 65 61 2 -19 75
/ \ / \ /
33 5 24 7 -10
WorkingTime[build_heap]: 0.02766 ms
______________77________
/ \
________69_______ ___75____
/ \ / \
___69__ _65 _61 _2
/ \ / \ / \ / \
_33 24 _39 10 38 2 -19 -1
/ \ / \ /
-3 5 6 7 -10
recursive version
build_heap: $T(n) = 2T(n/2) + O(logn)$ \(n^{log_2^2} > logn \\ \therefore T(n) = O(n)\) divide conquer 를 통한 build heap c++
증명
\[\begin{align} T(n) = nT(1) + \sum_{k=0}^{(\log_2{n} - 1)}2^k \log_2(\frac {n} {2^k}) \end{align}\]stack exchange 에서 정리한 바에 의하면, $\sum_{k=0}^{(\log_2{n} - 1)}2^k \log_2(\frac {n} {2^k})$ term을 다음과 같이 정리할 수 있다. \(\begin{align} \sum_{k=1}^{m}2^k \log_2(\frac {n} {2^k}) &=\sum_{k=1}^{m}2^k(\log_2{n}-k)\\ &=\log_2{n}\sum_{k=1}^{m}2^k-\sum_{k=1}^{m}k2^k \\ &=\log_2{n}(2^{m+1}-2)-(m2^{m+1}-2^{m+1}+2) \\ \end{align}\)
Then we need to replace $m$ back by $log_2{n}$: \(\begin{align} T(n) &=\log_2{n}+2n\log_2{n}-2\log_2{n}-2n\log_2{n}+2n-2 \\ &=2n-\log_2{n}-2=\Theta(n) \end{align}\)
In [6]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@logging_time
def build_heap(a):
""" build max heap using divide and conquer. """
def heapify(i):
""" a[i] finds a proper position to satisfy heap-property. """
left, right = 2 * i + 1, 2 * i + 2
if left > len(a) - 1: return # base case
indices = [k for k in [left, right, i] if k < len(a)]
largest = max(indices, key=lambda idx: a[idx])
if i != largest:
a[largest], a[i] = a[i], a[largest]
heapify(largest)
def make_heap(i):
left, right = 2 * i + 1, 2 * i + 2
if left > len(a) - 1: return
[make_heap(k) for k in [left, right] if k < len(a)]
heapify(i)
make_heap(0)
In [7]:
1
2
3
a = [random.randint(int(- ratio * nrange), int((1 - ratio) * nrange)) for _ in range(size)]
build_heap(a, verbose=True)
plot(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
WorkingTime[build_heap]: 0.04268 ms
____________78_________
/ \
__________69_____ ____75___
/ \ / \
____67___ _55 _69 _75
/ \ / \ / \ / \
46 _49 18 42 -9 -6 19 53
/ \ / \ /
8 46 48 21 6
inseart and delete
insert
last index에 삽입 후, from bottom to up으로 heapify.
\[O(logn)\]
In [8]:
1
2
3
4
5
6
7
8
9
10
11
12
@logging_time
def heappush(a:list, x):
""" insert new key `x` into heap `a`. """
def _siftup(i):
""" heapify bottom to up. """
up = (i - 1) // 2
if up < 0: return # base case
if a[up] < a[i]:
a[up], a[i] = a[i], a[up]
_siftup(up)
a.append(x)
_siftup(len(a) - 1)
In [9]:
1
2
3
4
5
a = [random.randint(int(- ratio * nrange), int((1 - ratio) * nrange)) for _ in range(size)]
build_heap(a, verbose=True)
plot(a)
heappush(a, 60, verbose=True)
plot(a)
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
WorkingTime[build_heap]: 0.04458 ms
____________68________
/ \
_________67_____ ____55___
/ \ / \
____51___ 26 50 _38
/ \ / \ / \ / \
_34 _33 _0 -3 7 17 -9 28
/ \ / \ /
27 -5 17 7 -2
WorkingTime[heappush]: 0.00286 ms
_______________68________
/ \
_________67________ ____55___
/ \ / \
____51___ ___60 50 _38
/ \ / \ / \ / \
_34 _33 _26 -3 7 17 -9 28
/ \ / \ / \
27 -5 17 7 -2 0
delete
last index에 있는 element(key 값)를 삭제하고 싶은 element 위치로 가져다 놓으면,
heap property가 깨지며, heapsize가 줄어든다.
다시 heap property를 만족하도록 그 위치에서 heapify한다.
heapify 할때, max heap을 기준으로 위로 heapify하는 _siftup, 아래로 heapify하는 _siftdown 이 있다.
old 값을 삭제할 노드의 key값, new를 last index에 있는 key값이라고하면, 다음과 같은 action을 취한다.
old < new:_siftup(i)old > new:_siftdown(i)old = new:nothingi는 삭제하고 싶은 key의 인덱스임에 유의
In [10]:
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
@logging_time
def heappop(a: list, i):
""" pop index i-th element. """
def _siftdown(i):
""" heapify up to bottom. """
left, right = 2 * i + 1, 2 * i + 2
if left > len(a) - 1: return
indices = [k for k in [left, right, i] if k < len(a) - 1]
largest = max(indices, key=lambda idx: a[idx])
if i != largest:
a[largest], a[i] = a[i], a[largest]
_siftdown(largest)
def _siftup(i):
""" heapify bottom to up. """
up = (i - 1) // 2
if up < 0: return # base case
if a[up] < a[i]:
a[up], a[i] = a[i], a[up]
_siftup(up)
old, new = a[i], a[-1]
a[i] = new
a.pop()
if len(a) > 1:
_siftup(i) if new < old else _siftdown(i)
return old
In [11]:
1
2
3
4
5
a = [random.randint(int(- ratio * nrange), int((1 - ratio) * nrange)) for _ in range(size)]
build_heap(a, verbose=True)
plot(a)
print("pop {}".format(heappop(a, 4, verbose=True)))
plot(a)
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
WorkingTime[build_heap]: 0.04339 ms
_____________79__________
/ \
__________76______ _____35___
/ \ / \
____68___ _74 _23_ _30
/ \ / \ / \ / \
_43 _67 _62 64 15 -15 16 -5
/ \ / \ /
31 -7 54 23 -4
WorkingTime[heappop]: 0.00381 ms
pop 74
__________79__________
/ \
__________76___ _____35___
/ \ / \
____68___ _-4 _23_ _30
/ \ / \ / \ / \
_43 _67 62 64 15 -15 16 -5
/ \ / \
31 -7 54 23
heap sort
heap을 만들어 놓고 생각하면, 직관적으로 sort되는 과정은 쉽다.
increasing order로 sort한다고 가정해보자.
- 먼저 max heap을 만든다.
- max heap의 root는 모든 원소중에 가장 큰 원소다. 따라서 그 값이 sorting순서의 마지막이다.
- heap에서 마지막 원소와 root(인덱스 첫번째)원소를 교환한다. (교환했으니 heap property가 깨짐.)
- heap size를 하나 줄여 이미 sorted order가 결정된 마지막 원소를 제외시키고, 마지막 인덱스를 하나 줄이자.
- root에 대해 heap property가 깨져 있으니, heapify(root index)를 통해 다시 heap property를 만족시키자.
implementation
\[T(n) = O(nlogn)\]heap size를 줄여나가야 하므로 heapify의 인자로 size
n을 받도록 하자.
In [12]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@logging_time
def heapsort(a):
def heapify(i, n):
""" a[i] finds a proper position to satisfy heap-property.
let n be argument because heapsize has to be decreased to sort. """
left, right = 2*i+1, 2*i+2
if left > n - 1: return # base case
indices = [k for k in [left, right, i] if k < n]
largest = max(indices, key=lambda idx: a[idx])
if i != largest:
a[largest], a[i] = a[i], a[largest]
heapify(largest, n)
build_heap(a)
for i in range(len(a) - 1 , 0, - 1):
a[i], a[0] = a[0], a[i]
heapify(0, n=i)
In [13]:
1
2
3
4
a = [random.randint(int(- ratio * nrange), int((1 - ratio) * nrange)) for _ in range(size)]
print(a)
heapsort(a, verbose=True)
print(a)
1
2
3
4
[29, 53, 14, 29, 22, 22, 66, 58, -10, 60, 11, 24, 14, 7, 48, 63, 75, 7, 45, 27]
WorkingTime[heapsort]: 0.12302 ms
[-10, 7, 7, 11, 14, 14, 22, 22, 24, 27, 29, 29, 45, 48, 53, 58, 60, 63, 66, 75]
library
heapq document
geeksforgeeks에서 사용법과 예제들 있다.
heapq 는 max heap에 대해 사용하기에는
heapq._heappush_max가 없으므로 주의하자.
In [14]:
1
import heapq
In [15]:
1
2
3
4
5
6
a = [random.randint(int(- ratio * nrange), int((1 - ratio) * nrange)) for _ in range(size)]
plot(a)
heapq.heapify(a) # build min heap
plot(a)
print("pop {} from heap a. ".format(heapq.heappop(a)))
plot(a)
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
_____________66_________
/ \
_________-9______ ____3__
/ \ / \
____32___ _18 _39 30
/ \ / \ / \ / \
_63 _21 _30 35 33 19 1 -9
/ \ / \ /
39 26 46 5 43
_____________-9_________
/ \
_________-9______ ____1___
/ \ / \
____5___ _18 _19 _3
/ \ / \ / \ / \
_26 _21 _30 35 33 39 66 30
/ \ / \ /
39 63 46 32 43
pop -9 from heap a.
_________-9_________
/ \
__________5___ ____1___
/ \ / \
____21___ _18 _19 _3
/ \ / \ / \ / \
_26 _32 30 35 33 39 66 30
/ \ / \
39 63 46 43
heappop의 구현과정을 생각해보면,
지울 인덱스(여기서는 항상 첫번째)에 있는 key와 마지막 인덱스에있는 key를 교환후,
size를 줄이고, heapify를 한다.
그 기본 연산을 기억하면, heapsort를 heapq모듈을 사용하여 구현하는 것이 쉽다.
heapsort이후,
a가 삭제되고 새로운 sorted array가 생성됨에 유의하자.
In [16]:
1
2
3
def heapsort(a):
heapq.heapify(a)
return [heapq.heappop(a) for _ in range(len(a))]
In [17]:
1
2
3
4
5
a = [random.randint(int(- ratio * nrange), int((1 - ratio) * nrange)) for _ in range(size)]
plot(a)
print(heapsort(a))
plot(a)
print(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
_____________7_________
/ \
__________13______ ____48___
/ \ / \
____16___ _11 _-1 _43
/ \ / \ / \ / \
_51 _24 _43 70 -7 27 57 -9
/ \ / \ /
57 73 23 -7 75
[-9, -7, -7, -1, 7, 11, 13, 16, 23, 24, 27, 43, 43, 48, 51, 57, 57, 70, 73, 75]
None
[]
Practice
Last Stone Weight
mycode
max heap으로 문제를 풀어야했기에 heapq 모듈을 썼어도, heappop()과 heappush() 대한 구현이 필요했다.
In [18]:
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
class Solution(object):
def lastStoneWeight(self, stones):
"""
:type stones: List[int]
:rtype: int
"""
def heappop():
def _heapify(i):
left, right = 2 * i + 1, 2 * i + 2
if left > len(stones) - 1: return
indices = [k for k in [left, right, i] if k < len(stones)]
largest = max(indices, key=lambda idx: stones[idx])
if i != largest:
stones[i], stones[largest] = stones[largest], stones[i]
_heapify(largest)
ans = stones[0]
stones[0] = stones[-1]
stones.pop()
_heapify(0)
return ans
def heappush(x):
def _heapify(i):
up = i - 1 >> 1
if up < 0: return
if stones[up] < stones[i]:
stones[up], stones[i] = stones[i], stones[up]
_heapify(up)
stones.append(x)
_heapify(len(stones) - 1)
if len(stones) == 1: return stones[-1]
heapq._heapify_max(stones) # O(n)
# O(nlogn)
while len(stones) > 1:
y = heappop() # O(logn)
x = heappop()
if y - x != 0:
heappush(y - x) # O(logn)
return stones[-1] if stones != [] else 0
In [19]:
1
2
sol = Solution()
print(sol.lastStoneWeight([2,7,4,1,8,1]))
1
2
1
discuss
lee215의 풀이에서,
어짜피 stones은 양수이므로 -를 붙히면, minheap으로 maxheap을 표현할 수 있다는 것을 배웠다.
또한, while문 조건에 h[0] != 0을 붙힘으로 인해 stones 이 []가 될때도 break하도록 하였다.
매우 짧은 코드를 만들 수 있었다.
In [20]:
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def lastStoneWeight(self, stones):
"""
:type stones: List[int]
:rtype: int
"""
h = [-x for x in stones]
heapq.heapify(h)
while len(h) > 1 and h[0] != 0:
heapq.heappush(h, heapq.heappop(h) - heapq.heappop(h))
return -h[0] # revert to positive
In [21]:
1
2
sol = Solution()
print(sol.lastStoneWeight([2,7,4,1,8,1]))
1
2
1
Network Delay Time - Dijkstra Algorithm
This algorithm is described in this posting
Report
heap은 priority (key) sorting에 유리
binary search tree는 searching에 유리
complete binary tree에서 child와 parent 에 접근할때 bit연산을 이용할 수 있다. python operator prioirity
In [22]:
1
2
3
4
left = lambda i: (i << 1) + 1 # 1 shift and plus 1
right = lambda i: (i << 1) + 2 # 1 shift and plus 2
parent = lambda i: i - 1 >> 1 # minus 1 and shift
left(1), right(1), parent(1)
1
(3, 4, 0)
Reference
[1] ratsgo’s blog
Leave a comment