Dequeue

HNode* Heap::dequeue() {
    HNode* tree_root = tree[1];

    int index = tree.size() - 1;
    HNode* last = tree[index];
    tree.pop_back();

    if (index > 0) {
        tree[1] = last;
        // fixheap
        HNode* root = tree[1];
        int last_index = tree.size() - 1;
        int other_index = 1;
        bool more = true;
        while (more) {
            int child_index = 2 * other_index;
            if (child_index <= last_index) {
                HNode* child = tree[2*index];
                if ((2*index + 1 <= last_index) && tree[2*index+1]->weight < child->weight) {
                    child_index = 2 * other_index + 1;
                    child = tree[2*other_index+1];
                }
                if (child->weight < root->weight) {
                    tree[other_index] = child;
                    child = tree[2*other_index+1];
                }
                else {
                    more = false;
                }
            }
            else {
                more = false;
            }
        }
        tree[other_index] = root;
    }
    count--;
    return tree_root;
}