public HeapNode extractMin() throws Exception {
        if (this.lastFreePos == 0) {
            throw new Exception("Empty heap");
        }
        // It 's basicly a deletion from the first position without needing to bubble up
        HeapNode hn = this.heapNodes[0], aux;
        this.heapNodes[0] = this.heapNodes[this.lastFreePos - 1];
        this.positions[this.heapNodes[0].vertex] = 0;
        this.heapNodes[this.lastFreePos - 1] = null;
        this.positions[hn.vertex] = -1;
        this.lastFreePos--;
        
        /* bubble down */
        int parentPos = 0, leftChildPos = (parentPos + 1) * 2 - 1, rightChildPos = leftChildPos + 1, minChildPos;
        while ((leftChildPos < this.lastFreePos && this.heapNodes[parentPos].compareTo(this.heapNodes[leftChildPos]) > 0)
                || (rightChildPos < this.lastFreePos && this.heapNodes[parentPos].compareTo(this.heapNodes[rightChildPos]) > 0)) {
            minChildPos = leftChildPos;
            if (rightChildPos < this.lastFreePos && this.heapNodes[leftChildPos].compareTo(this.heapNodes[rightChildPos]) > 0) {
                minChildPos = rightChildPos;
            }
            aux = this.heapNodes[parentPos];
            this.heapNodes[parentPos] = this.heapNodes[minChildPos];
            this.heapNodes[minChildPos] = aux;
            this.positions[this.heapNodes[minChildPos].vertex] = minChildPos;
            this.positions[this.heapNodes[parentPos].vertex] = parentPos;
            parentPos = minChildPos;
            leftChildPos = (parentPos + 1) * 2 - 1;
            rightChildPos = leftChildPos + 1;
        }
        return hn;
    }