removeFirst method

(int, double) removeFirst()

Removes and returns the smallest element in the queue, and its priority.

The queue must not be empty.

Implementation

(int, double) removeFirst() {
  final top = first;
  _length--;

  if (_length > 0) {
    final id = _ids.first = _ids[_length];
    final priority = _priorities.first = _priorities[_length];
    final halfLength = _length ~/ 2;

    var pos = 0;
    while (pos < halfLength) {
      var left = (pos << 1) + 1;
      final right = left + 1;
      var minId = _ids[left];
      var minPriority = _priorities[left];
      final rightPriority = _priorities[right];

      if (right < _length && rightPriority < minPriority) {
        left = right;
        minId = _ids[right];
        minPriority = rightPriority;
      }
      if (minPriority >= priority) {
        break;
      }

      _ids[pos] = minId;
      _priorities[pos] = minPriority;
      pos = left;
    }

    _ids[pos] = id;
    _priorities[pos] = priority;
  }

  return top;
}