@Test
    public void extractMinTest() {
        int i, j, heapDimension;
        HeapNode minHNode = null;
        Random randomGenerator = new Random();
        heapDimension = 100 + randomGenerator.nextInt(200);
        MinHeap heap = new MinHeap(heapDimension);

        try {
            heap.extractMin();
            fail("Heap should be empty.");
        } catch (Exception ex) {
            assertEquals(ex.getMessage(), "Empty heap");
        }

        for (i = 0; i < heapDimension; i++) {
            try {
                heap.insert(new HeapNode(i, 0, 1 + randomGenerator.nextInt(200)));
            } catch (Exception ex) {
                fail("Exception was not expected to be thrown.");
            }
        }

        for (i = 0; i < heapDimension; i++) {
            try {
                minHNode = heap.extractMin();
            } catch (Exception ex) {
                fail("Exception was not expected to be thrown.");
            }

            assertEquals(heap.lastFreePos, heapDimension - i - 1);
            assertTrue(heap.positions[minHNode.vertex] == -1);

            for (j = 0; j < heap.lastFreePos; j++) {
                assertEquals(j, heap.positions[heap.heapNodes[j].vertex]);

                if ((j + 1) * 2 - 1 < heap.lastFreePos) {
                    assertTrue(heap.heapNodes[j].compareTo(heap.heapNodes[(j + 1) * 2 - 1]) <= 0);
                } else {
                    continue;
                }
                if ((j + 1) * 2 < heap.lastFreePos) {
                    assertTrue(heap.heapNodes[j].compareTo(heap.heapNodes[(j + 1) * 2]) <= 0);
                }
            }
        }
    }