有界优先级队列 是一个有元素最大限制的优先级队列。如果一个新的元素插入到有界优先级队列中，但是容量已经最大了，那么先把优先级中最不优先的元素移除，然后插入。
例子一：
Value: [ A, B, C, D, E ]
Priority: [ 0.1, 0.25, 1.33, 3.2, 4.6 ]
从优先级来说 A > B > C > D > E 如果将优先级F 0.4加入。由于我们限制最大容量是5，所以将最不重要的 E 移除掉，加入F。
由于F 的优先级值决定其被插入 B 与 C之间。
Value: [ A, B, F, C, D ]
Priority: [ 0.1, 0.25, 0.4, 1.33, 3.2 ]
如果在加入新元素G 其优先级4.0，则会因为其优先级值大于优先级其他元素，所以不需要加入。
代码实现
//堆最后一个元素
id tailObj = [self.heap lastObject];
//min-heap
if (self.ordering == DSHeapOrderingAscending)
{
//如果最小堆 后面添加的元素比之前的“大”那么不用添加
if (NSOrderedAscending == [self.comparator(tailObj](http://self.comparator(tailobj/),obj))
{
return;
}
//如果满足条件删除最后一个元素 并且插进去
else
{
[self.heap removeObject:tailObj];
[self.heap addObject:obj];
}
例子二：
Value: [ A, B, C, D, E ]
Priority: [ 4.6, 3.2, 1.33, 0.25, 0.1 ]
从游戏那几来说 A > B > C > D > E 如果将优先级 0.4加入。由于我们限制最大的容量是5，所以将最不重要的 E 移除掉，加入F。由于0.4优先级决定插入C和D之间。
Value: [ A, B, C, F, D ]
Priority: [ 4.6, 3.2, 1.33, 0.4, 0.25 ]
如果再加入新元素G 0.1 ，由于G 的优先级比最小的优先级元素还小，所以不需要加入。
代码实现
//如果最大堆 后面添加的元素比之前的“小”那么不用添加
if (NSOrderedDescending == [self.comparator(tailObj](http://self.comparator(tailobj/),obj))
{
return;
}
//如果满足条件删除最后一个元素 并且插进去
else
{
[self.heap removeObject:tailObj];
[self.heap addObject:obj];
}
参考链接：https://github.com/ksco/swift-algorithm-club-cn/tree/master/Bounded%20Priority%20Queue
网友评论