class Node(object):
"""
the type of class stored in the hashmap, in case there are many same heights
in the heap, maintain the number
"""
def __init__(self, id, num):
self.id = id #id means its id in heap array
self.num = num #number of same value in this id 处理重复元素
class HashHeap(object):
def __init__(self, mode):
self.heap = []
self.mode = mode
self.size = 0
self.hash = {}
def top(self):
return self.heap[0] if len(self.heap) > 0 else 0
def isempty(self):
return len(self.heap) == 0
def _comparesmall(self, a, b): #compare function in different mode
if a <= b:
if self.mode == 'min':
return True
else:
return False
else:
if self.mode == 'min':
return False
else:
return True
def _swap(self, idA, idB): #swap two values in heap, we also need to change
valA = self.heap[idA]
valB = self.heap[idB]
numA = self.hash[valA].num
numB = self.hash[valB].num
self.hash[valB] = Node(idA, numB)
self.hash[valA] = Node(idB, numA)
self.heap[idA], self.heap[idB] = self.heap[idB], self.heap[idA]
def add(self, now): #the key, height in this place
self.size += 1
if self.hash.get(now):
hashnow = self.hash[now]
self.hash[now] = Node(hashnow.id, hashnow.num + 1)
else:
self.heap.append(now)
self.hash[now] = Node(len(self.heap) - 1,1)
self._siftup(len(self.heap) - 1)
def delete(self, now):
self.size -= 1
hashnow = self.hash[now]
id = hashnow.id
num = hashnow.num
if num == 1:
self._swap(id, len(self.heap)-1) #like the common delete operation
self.hash.pop(now)
self.heap.pop()
if len(self.heap) > id:
self._siftup(id)
self._siftdown(id)
else:
self.hash[now] = Node(id, num - 1)
def parent(self, id):
if id == 0:
return -1
return (id - 1) / 2
def _siftup(self,id):
while abs(id -1)/2 < id : #iterative version
parentId = (id - 1)/2 #这里非常tricky.
if self._comparesmall(self.heap[parentId],self.heap[id]):
break
else:
self._swap(id, parentId)
id = parentId
def _siftdown(self, id): #iterative version
while 2*id + 1 < len(self.heap):
l = 2*id + 1
r = l + 1
small = id
if self._comparesmall(self.heap[l], self.heap[id]):
small = l
if r < len(self.heap) and self._comparesmall(self.heap[r], self.heap[small]):
small = r
if small != id:
self._swap(id, small)
else:
break
id = small
这个hashheap的实现可以既可以是最大堆,也可以是最小堆,同时因为hash表中存的value是在heap数组中的index和这个key值的数目,所以可以处理重复数字.关键在于siftup和siftdown的非递归实现.siftdown相当于heapify,但是之前只使用过递归版本.