Python 的 treemap

python里没有按key排序的字典，类似于Java里treemap那种，导致很麻烦。
研究了一下，用heapq或者bisect都没法模拟treemap，关键是remove操作没法做到O(logn). 第三方库倒是有，但是没法在Online Judgement上用。
跪求各位python大佬的解决办法~

用python做题，不会被鄙视吗？

白板你可以唬烂一个，面试官非得让你写的话也行，基本就是wrap一个heapq，删除时记录删除次数，pop时如果当前值已经被删过那就继续pop。。如果面试官看见python就鄙视，可能是面试官水平不够吧，之前面亚麻碰到过两次

1，自己写（但在面试的时候，不现实）

补充内容 (2018-6-23 08:41):
没写完，就发出来了。2，据说这种情况下可以用less optimal的数据结构，面试官心里也有数的。

楼主可以参考，

In [20]: from collections import OrderedDict

In [21]: values = list(range(0, 10))

In [22]: OrderedDict({values[i]: values[::-1][i] for i, k in enumerate(values)})
Out[22]:
OrderedDict([(0, 9),
             (1, 8),
             (2, 7),
             (3, 6),
             (4, 5),
             (5, 4),
             (6, 3),
             (7, 2),
             (8, 1),
             (9, 0)])


补充内容 (2018-6-26 19:00):
啊，不好意思没审题

你换成java语言不得了，非得拘泥一个？

不是有lambda expression？ 我查查。。

daddev 发表于 2018-6-25 13:39
用python做题，不会被鄙视吗？

肯定不会啊。面试也有鄙视链的么

umialpha 发表于 2018-6-25 14:43
肯定不会啊。面试也有鄙视链的么

反正我面试的时候，要是candidate用Python，我第一反应就是：这哥们儿适合做SRE/OPS.

补充内容 (2018-6-26 12:45):
几年前，或者早期Start up用python写后端最近还是很普遍的，上手快，出活儿。面试主要考察思路和代码，但是用python感觉还是很怪。

糊了一个简易实现，不过元素数量上10^5 ~ 10^6之后就性能爆炸了...

1. class TreeNode:
   
2.     def __init__(self, slots = None, links = None):
   
3.         self.slots = slots or []
   
4.         self.links = links or [None]
   
5. 
   
6.     def getKey(self, pos):
   
7.         return self.slots[pos][0]
   
8. 
   
9.     def insertSlot(self, pos, slot, link, degree):
   
10.         self.slots.insert(pos, slot)
    
11.         self.links.insert(pos, link)
    
12.         sibling = popup = None
    
13.         if len(self.slots) > degree * 2:
    
14.             # Split
    
15.             sibling = TreeNode(self.slots[:degree], self.links[:degree+1])
    
16.             popup = self.slots[degree]
    
17.             self.slots = self.slots[-degree:]
    
18.             self.links = self.links[-degree-1:]
    
19.         return (slot, sibling, popup)
    
20. 
    
21. # B Tree.
    
22. class TreeMap:
    
23.     def __init__(self, degree = 8):
    
24.         self.degree = degree
    
25.         self.root = TreeNode()
    
26.         self.size = 0
    
27. 
    
28.     def __setitem__(self, key, value):
    
29.         slot = self._locateSlot([], self.root, key, True)
    
30.         slot[1] = value
    
31.         if not slot[2]:
    
32.             slot[2] = True
    
33.             self.size += 1
    
34. 
    
35.     def __getitem__(self, key):
    
36.         slot = self._locateSlot([], self.root, key, False)
    
37.         if slot is None or not slot[2]:
    
38.             raise Exception('key "' + str(key) + '" does not exist')
    
39.         return slot[1]
    
40. 
    
41.     def __len__(self):
    
42.         return self.size
    
43. 
    
44.     def pop(self, key):
    
45.         # Mark as deleted
    
46.         slot = self._locateSlot([], self.root, key, False)
    
47.         if slot is not None and slot[2]:
    
48.             slot[2] = False
    
49.             self.size -= 1
    
50.             return slot[1]
    
51.         return None
    
52. 
    
53.     def range(self, lower_bound, upper_bound):
    
54.         for slot in self._traverse(self.root, lower_bound, upper_bound):
    
55.             if slot[2]:
    
56.                 yield (slot[0], slot[1])
    
57. 
    
58.     def _traverse(self, node, lower_bound, upper_bound):
    
59.         size = len(node.slots)
    
60.         begin = next(i for i in range(size+1) if i == size or node.getKey(i) >= lower_bound)
    
61.         for i in range(begin, size+1):
    
62.             if node.links[i] is not None:
    
63.                 for slot in self._traverse(node.links[i], lower_bound, upper_bound):
    
64.                     yield slot
    
65.             if i == size or node.getKey(i) > upper_bound:
    
66.                 break
    
67.             yield node.slots[i]
    
68. 
    
69.     def _locateSlot(self, ancestors, node, key, insert):
    
70.         size = len(node.slots)
    
71.         pivot = next(i for i in range(size + 1) if i == size or key <= node.getKey(i))
    
72.         if pivot != size and node.getKey(pivot) == key:
    
73.             return node.slots[pivot]
    
74.         child = node.links[pivot]
    
75.         ancestors.append((node, pivot))
    
76.         return self._locateSlot(ancestors, child, key, insert) if child is not None \
    
77.           else self._insertSlot(ancestors, [key, None, False], None) if insert \
    
78.           else None
    
79. 
    
80.     def _insertSlot(self, ancestors, slot, link):
    
81.         node, pos = ancestors.pop()
    
82.         slot, sibling, popup = node.insertSlot(pos, slot, link, self.degree)
    
83.         if sibling is not None:
    
84.             if len(ancestors) == 0:
    
85.                 self.root = TreeNode([popup], [sibling, node])
    
86.             else:
    
87.                 self._insertSlot(ancestors, popup, sibling)
    
88.         return slot
    
89. 
    
90. 
    
91. # Example.
    
92. from sys import stdout
    
93. 
    
94. tree = TreeMap()
    
95. tree["A"] = 1
    
96. tree["B"] = 2
    
97. tree["C"] = 3
    
98. tree["D"] = 4
    
99. tree["E"] = 5
    
100. tree["F"] = 6
     
101. tree["G"] = 7
     
102. 
     
103. stdout.write("Before, # of entries = " + str(len(tree)) + "\n")
     
104. 
     
105. tree.pop("C")
     
106. tree.pop("E")
     
107. 
     
108. stdout.write("After, # of entries = " + str(len(tree)) + "\n")
     
109. 
     
110. for key, value in tree.range("B", "F"):
     
111.     stdout.write("[" + key + "]: " + str(value) + "\n")

复制代码