| 121 | // elements. This is an O(log n) operation. Must not be called when the queue |
| 122 | // is empty. |
| 123 | T IR_ALWAYS_INLINE Pop() { |
| 124 | if (Size() > 0) { |
| 125 | int last = Size() - 1; |
| 126 | T top_element = Top(); |
| 127 | // Swap the top element from 0 to index 'last'. |
| 128 | Swap(elements_[0], elements_[last]); |
| 129 | // Heapify from index 0 and down. |
| 130 | HeapifySubtreeDown(0, last); |
| 131 | elements_.pop_back(); |
| 132 | // Return the original top element. |
| 133 | return top_element; |
| 134 | } |
| 135 | DCHECK(false); |
| 136 | return T(); |
| 137 | } |
| 138 | |
| 139 | // Heapify from top element at index 0 in O(log n) complexity. It is |
| 140 | // assumed that the elements in [1, size_-1] are already arranged as a heap. |