Heap
常见操作:
pop(): 把堆顶和最后一个元素swap,然后删除最后一个元素,再siftdown,和两个子节点相比较(i 2 + 1),(i 2 + 2),不满足就swap。 O(log n)
push(): 把新加入的元素加到末尾,然后siftup,和父亲节点(i - 1)/2 比较。O(log n)
peek(): O(1)
remove(): for循环找到要删除的元素,然后和队尾的元素交换,再根据需要看是否需要siftup或者siftdown。O(n)
如何提高? 瓶颈在查找上,所以可以用一个hashmap来加速查找。可以优化到O(log n).也就是HashHeap 如果允许重复怎么办?加一个count属性。