private void heapify(int i) {
        int smallest;
        int left = leftChild(i);
        int right = rightChild(i);
        if (right <= heap_size) {
            if (ar[left].getKey() < ar[right].getKey()) {
                smallest = left;
            } else {
                smallest = right;
            }
            if (ar[smallest].getKey() < ar[i].getKey()) {
                HeapNode xNode = ar[smallest];
                ar[smallest] = ar[i];
                ar[i] = xNode;
                heapify(smallest);
                ar[smallest].setIndex(smallest);
                ar[i].setIndex(i);
            }
        }
        if (left == heap_size && ar[i].getKey() > ar[left].getKey()) {
            HeapNode xNode = ar[i];
            ar[i] = ar[left];
            ar[left] = xNode;

            ar[i].setIndex(i);
            ar[left].setIndex(i);
        }
    }