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属性。

results matching ""

    No results matching ""