由于传统的堆并不支持对堆中除头和尾以外的位置的增删改，而在实际情况下我们需要对其他节点进行操作。这里我们在堆原有数据结构基础上进行扩展，
用’定位器‘来实现对堆中其他元素的定位。定位器是指在堆原有节点类中加入一个新属性_index（节点在底层数据结构数组中的秩），然后实列化节点类（locator），
并返回给用户用来定位每一个节点。
下面我们先展示基于原始堆的优先级排序数据结构的代码：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#python3
class HeapPriorityQueue:
class _Item:
def __init__(self, key, value):
self._key = key
self._val = value
def __lt__(self, other):
return self._key < other._key
### private behaviours
def _left(self, j):
return 2*j+2
def _right(self, j):
return 2*j+1
def _parent(self, j):
return (j-1)//2
def _has_left(self, j):
return self._left(j) < len(self._data)
def _has_right(self, j):
return self._right(j) < len(self._data)
def _swap(self, i, j):
self._data[i], self._data[j] = self._data[j], self._data[i]
def _downheap(self, j): #向下冒泡
if self._has_right(j):
small = self._right(j)
if self._has_left(j):
if self._data[self._left(j)] < self._data[small]:
small = self._left(j)
if self._data[small] < self._data[j]:
self._swap(small, j)
self._downheap(small)
def _upheap(self, j): #向上冒泡
if j > 0 and self._data[j] < self._data[self._parent(j)]:
self._swap(j, self._parent(j))
self._upheap(self._parent(j))
###public behaviours
def __init__(self):
self._data = []
def __len__(self):
return len(self._data)
def is_empty(self):
return len(self)==0
def add(self, k, v):
self._data.append(self._Item(k,v))
self._upheap(len(self._data)-1)
def min(self):
if self.is_empty():
raise ValueError('heap is empty')
return self._data[0]._key, self._data[0].val
def remove_min(self):
if self.is_empty():
raise ValueError
self._swap(0, len(self._data)-1)
item = self._data.pop()
self._downheap(0)
return (item._key, item._val)
接下来是适应性优先级队列，对于这个我们提供两种新方法：update（更新堆中某一节点），remove（删除某一节点）。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#python3
class AdapatablePriorityHeapQueue(HeapPriorityQueue):
class Locator(HeapProrityQueue._Item):
def __init__(self, k, v, index):
super().__init__(k,v)
self._index = index
### private behaviours
def _swap(self, i, j):
super()._swap(i, j)
self._data[i]._index = i
self._data[j]._index = j
def _bubble(self, j):
if 0<j and self._data[j] < self._data[self._parent(j)]:
self._upheap(j)
else:
self._downheap(j)
### public behaviours
def add(self, k, v):
loc = self.Locator(k, v, len(self))
self._data.append(loc)
self._upheap(len(self._data)-1)
return loc
def update(self, loc, k, v):
j = loc._index
if not (0<=j<len(self)) and self._data[j]==loc:
raise ValueError('invalid locator')
loc._key = k
loc._val = v
self._bubble(j)
def remove(self, loc):
j = loc._index
if not (0 <= j < len(self) and self._data[j]==loc):
raise ValueError('invalid locator')
if j != len(self)-1:
self._swap(j, len(self)-1)
self._bubble(j)
self._data.pop()
return (loc._key, loc._val)
