Q:说明如何使用优先级队列来实现一个先进先出队列，另说明如何用优先级队列来实现栈。
A:队列的性质是先进先出，所以维护一个最小优先级队列，给先进队的元素赋一个小的优先级，每插入一个新的元素优先级加1。 出队时取优先级最小的元素并维护优先级队列即可。栈的实现同理。
6.5-7
Q:HEAP-DELETE(A,i)操作将结点i中的项从堆A中删去。对含n个元素的最大堆，请给出时间为O(lgn)的HEAP-DELETE的实现。
A:类似于堆排序时做的操作，将要删除的结点和堆的最后一个结点交换，将其删除后维护堆的性质。伪代码:
Read full article from H.y's Blog
No comments:
Post a Comment