179 lines
4.4 KiB
Python
179 lines
4.4 KiB
Python
import math
|
|
|
|
class Node:
|
|
__slots__ = ('key', 'dist', 'left', 'right', 'parent', 'child', 'degree', 'lost')
|
|
|
|
def __init__(self, key, dist):
|
|
self.key = key
|
|
self.dist = dist
|
|
|
|
self.left = self
|
|
self.right = self
|
|
|
|
self.parent = None
|
|
self.child = None
|
|
|
|
self.degree = 0
|
|
self.lost = False
|
|
|
|
def connect_right(self, new_right):
|
|
old_right = self.right
|
|
new_left = new_right.left
|
|
|
|
new_right.left = self
|
|
new_left.right = old_right
|
|
|
|
old_right.left = new_left
|
|
self.right = new_right
|
|
|
|
def remove(self):
|
|
self.left.right = self.right
|
|
self.right.left = self.left
|
|
self.left = self
|
|
self.right = self
|
|
|
|
def connect_child(self, child):
|
|
child.parent = self
|
|
child.lost = False
|
|
|
|
if self.child is None:
|
|
self.child = child
|
|
else:
|
|
self.child.connect_right(child)
|
|
|
|
self.degree += 1
|
|
|
|
class FiboHeap:
|
|
def __init__(self, nodes):
|
|
self.min = None
|
|
self.n = 0
|
|
self.pos = [None] * nodes
|
|
|
|
def cut(self, cur):
|
|
p = cur.parent
|
|
if p.child is cur:
|
|
if cur.right is cur:
|
|
p.child = None
|
|
else:
|
|
p.child = cur.right
|
|
|
|
cur.remove()
|
|
p.degree -= 1
|
|
|
|
cur.parent = None
|
|
cur.lost = False
|
|
|
|
self.min.connect_right(cur)
|
|
if cur.dist < self.min.dist:
|
|
self.min = cur
|
|
|
|
def cascading_cut(self, cur):
|
|
while True:
|
|
p = cur.parent
|
|
if p is None:
|
|
return
|
|
if not cur.lost:
|
|
cur.lost = True
|
|
return
|
|
self.cut(cur)
|
|
cur = p
|
|
|
|
def add(self, key, dist):
|
|
cur = Node(key, dist)
|
|
|
|
if self.min is None:
|
|
self.min = cur
|
|
else:
|
|
self.min.connect_right(cur)
|
|
if cur.dist < self.min.dist:
|
|
self.min = cur
|
|
|
|
self.n += 1
|
|
self.pos[key] = cur
|
|
|
|
def extract_min(self):
|
|
# 1. Find min node
|
|
min_node = self.min
|
|
if min_node is None:
|
|
return None
|
|
self.n -= 1
|
|
|
|
# 2. Make min node's child into individual tree
|
|
c = min_node.child
|
|
if c is not None:
|
|
start = c
|
|
cur = c
|
|
while True:
|
|
cur.parent = None
|
|
cur.lost = False
|
|
cur = cur.right
|
|
if cur == start:
|
|
break
|
|
|
|
min_node.connect_right(start)
|
|
|
|
if min_node.right is min_node:
|
|
self.min = None
|
|
return (min_node.key, min_node.dist)
|
|
|
|
nxt = min_node.right
|
|
min_node.remove()
|
|
self.min = nxt
|
|
|
|
min_node.child = None
|
|
min_node.degree = 0
|
|
self.pos[min_node.key] = None
|
|
|
|
# 3. Make into binomial tree
|
|
roots = []
|
|
start = self.min
|
|
cur = start
|
|
while True:
|
|
roots.append(cur)
|
|
cur = cur.right
|
|
if cur == start:
|
|
break
|
|
|
|
max_deg = int(math.log2(self.n)) + 2 if self.n > 0 else 1 # 여기서 +2 하는 이유는 사실은 log2가 아니라 fibonacci 수열 기반이기 때문에 +1 더 해주는 거임.
|
|
A = [None] * (max_deg + 1)
|
|
|
|
for cur in roots:
|
|
x = cur
|
|
d = x.degree
|
|
|
|
while A[d] is not None:
|
|
y = A[d]
|
|
if y.dist < x.dist:
|
|
x, y = y, x
|
|
y.remove()
|
|
x.connect_child(y)
|
|
A[d] = None
|
|
d = x.degree
|
|
A[d] = x
|
|
|
|
# 4. Find new min
|
|
self.min = None
|
|
for cur in A:
|
|
if cur is None:
|
|
continue
|
|
if self.min is None:
|
|
self.min = cur
|
|
else:
|
|
if cur.dist < self.min.dist:
|
|
self.min = cur
|
|
|
|
return (min_node.key, min_node.dist)
|
|
|
|
def decrease_key(self, key, new_dist):
|
|
cur = self.pos[key]
|
|
if cur is None or new_dist >= cur.dist:
|
|
return
|
|
cur.dist = new_dist
|
|
p = cur.parent
|
|
|
|
if p is not None and cur.dist < p.dist:
|
|
self.cut(cur)
|
|
self.cascading_cut(p)
|
|
|
|
if cur.dist < self.min.dist:
|
|
self.min = cur |