224 lines
5.6 KiB
Python
224 lines
5.6 KiB
Python
''' mbinary
|
|
#########################################################################
|
|
# File : leftHeap.py
|
|
# Author: mbinary
|
|
# Mail: zhuheqin1@gmail.com
|
|
# Blog: https://mbinary.xyz
|
|
# Github: https://github.com/mbinary
|
|
# Created Time: 2018-05-19 23:06
|
|
# Description:
|
|
#########################################################################
|
|
'''
|
|
|
|
from functools import total_ordering
|
|
|
|
|
|
@total_ordering
|
|
class node:
|
|
def __init__(self, val, freq=1, s=1, left=None, right=None):
|
|
self.val = val
|
|
self.freq = freq
|
|
self.s = s
|
|
if left is None or right is None:
|
|
self.left = left if left is not None else right
|
|
self.right = None
|
|
else:
|
|
if left.s < right.s:
|
|
left, right = right, left
|
|
self.left = left
|
|
self.right = right
|
|
self.s += self.right.s
|
|
|
|
def __eq__(self, nd):
|
|
return self.val == nd.val
|
|
|
|
def __lt__(self, nd):
|
|
return self.val < nd.val
|
|
|
|
def __repr__(self):
|
|
return 'node(val=%d,freq=%d,s=%d)' % (self.val, self.freq, self.s)
|
|
|
|
|
|
class leftHeap:
|
|
def __init__(self, root=None):
|
|
self.root = root
|
|
|
|
def __bool__(self):
|
|
return self.root is not None
|
|
|
|
@staticmethod
|
|
def _merge(root, t): # -> int
|
|
if root is None:
|
|
return t
|
|
if t is None:
|
|
return root
|
|
if root < t:
|
|
root, t = t, root
|
|
root.right = leftHeap._merge(root.right, t)
|
|
if root.left is None or root.right is None:
|
|
root.s = 1
|
|
if root.left is None:
|
|
root.left, root.right = root.right, None
|
|
else:
|
|
if root.left.s < root.right.s:
|
|
root.left, root.right = root.right, root.left
|
|
root.s = root.right.s+1
|
|
return root
|
|
|
|
def insert(self, nd):
|
|
if not isinstance(nd, node):
|
|
nd = node(nd)
|
|
if self.root is None:
|
|
self.root = nd
|
|
return
|
|
if self.root == nd:
|
|
self.root.freq += 1
|
|
return
|
|
prt = self. _findPrt(self.root, nd, None)
|
|
if prt is None:
|
|
self.root = leftHeap._merge(self.root, nd)
|
|
else:
|
|
if prt.left == nd:
|
|
prt.left.freq += 1
|
|
else:
|
|
prt.right.freq += 1
|
|
|
|
def remove(self, nd):
|
|
if not isinstance(nd, node):
|
|
nd = node(nd)
|
|
if self.root == nd:
|
|
self.root = leftHeap._merge(self.root.left, self.root.right)
|
|
else:
|
|
prt = self._findPrt(self.root, nd, None)
|
|
if prt is not None:
|
|
if prt.left == nd:
|
|
prt.left = leftHeap._merge(prt.left.left, prt.left.right)
|
|
else:
|
|
prt.right = leftHeap._merge(
|
|
prt.right.left, prt.right.right)
|
|
|
|
def find(self, nd):
|
|
if not isinstance(nd, node):
|
|
nd = node(nd)
|
|
prt = self._findPrt(self.root, nd, self.root)
|
|
if prt is None or prt == nd:
|
|
return prt
|
|
elif prt.left == nd:
|
|
return prt.left
|
|
else:
|
|
return prt.right
|
|
|
|
def _findPrt(self, root, nd, parent):
|
|
if not isinstance(nd, node):
|
|
nd = node(nd)
|
|
if root is None or root < nd:
|
|
return None
|
|
if root == nd:
|
|
return parent
|
|
l = self._findPrt(root.left, nd, root)
|
|
return l if l is not None else self._findPrt(root.right, nd, root)
|
|
|
|
def getTop(self):
|
|
return self.root
|
|
|
|
def pop(self):
|
|
nd = self.root
|
|
self.remove(self.root.val)
|
|
return nd
|
|
|
|
def levelTraverse(self):
|
|
li = [(self.root, 0)]
|
|
cur = 0
|
|
while li:
|
|
nd, lv = li.pop(0)
|
|
if cur < lv:
|
|
cur = lv
|
|
print()
|
|
print(nd, end=' ')
|
|
else:
|
|
print(nd, end=' ')
|
|
if nd.left is not None:
|
|
li.append((nd.left, lv+1))
|
|
if nd.right is not None:
|
|
li.append((nd.right, lv+1))
|
|
|
|
|
|
if __name__ == '__main__':
|
|
lh = leftHeap()
|
|
data = [(i-3)**2 for i in range(20)]
|
|
for i in data:
|
|
lh . insert(i)
|
|
lh.levelTraverse()
|
|
print()
|
|
for i in data:
|
|
print(lh.getTop())
|
|
if lh.find(i) is not None:
|
|
lh.remove(i)
|
|
'''
|
|
data = [(i-10)**2 for i in range(20)]
|
|
node(100,freq=1,s=3)
|
|
node(81,freq=2,s=3) node(64,freq=2,s=2)
|
|
node(16,freq=2,s=2) node(25,freq=2,s=2) node(49,freq=2,s=1) node(36,freq=2,s=1)
|
|
node(9,freq=2,s=1) node(4,freq=2,s=1) node(1,freq=2,s=1) node(0,freq=1,s=1)
|
|
node(100,freq=1,s=3)
|
|
node(81,freq=2,s=3)
|
|
node(64,freq=2,s=2)
|
|
node(49,freq=2,s=1)
|
|
node(36,freq=2,s=3)
|
|
node(25,freq=2,s=2)
|
|
node(16,freq=2,s=2)
|
|
node(9,freq=2,s=1)
|
|
node(4,freq=2,s=2)
|
|
node(1,freq=2,s=1)
|
|
node(0,freq=1,s=1)
|
|
None
|
|
None
|
|
None
|
|
None
|
|
None
|
|
None
|
|
None
|
|
None
|
|
None
|
|
'''
|
|
|
|
'''
|
|
data = [(i-3)**2 for i in range(20)]
|
|
node(256,freq=1,s=1)
|
|
node(225,freq=1,s=1)
|
|
node(196,freq=1,s=1)
|
|
node(169,freq=1,s=1)
|
|
node(144,freq=1,s=1)
|
|
node(121,freq=1,s=1)
|
|
node(100,freq=1,s=1)
|
|
node(81,freq=1,s=1)
|
|
node(64,freq=1,s=1)
|
|
node(49,freq=1,s=1)
|
|
node(36,freq=1,s=1)
|
|
node(25,freq=1,s=1)
|
|
node(16,freq=1,s=1)
|
|
node(9,freq=2,s=2)
|
|
node(4,freq=2,s=1) node(1,freq=2,s=1)
|
|
node(0,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
node(256,freq=1,s=1)
|
|
'''
|