使用minHeapify（）对数组进行排序，并使用extractMin（）返回元素

debugcn 发表于 Dev

非约翰

我正在使用minHeapify结构从数组中提取数字，并使用此方法“ minHeapify（）”对数组进行排序，并使用extractMin（）返回具有最小值的元素。

它总是总是首先返回第一个元素，并且在计算负数时遇到了麻烦。这是我的代码，

    public class PQHeap implements PQ {

    Element[] eList;
    int size;

    public PQHeap(int maxElms){
        eList= new Element[maxElms];
    }

    @Override
    public Element extractMin() {
        size = heapSize(eList);
        if (size <= 0) {
            System.out.println("Empty Array");
            return null;
        }
        Element min = eList[0];
        eList[0] = eList[size -1];
        // sets the last index in the array to null
        eList[size -1]= null;
        size--;
        minHeapify(eList, 0);
        return min;
    }

    public void minHeapify(Element[] array, int num){
        int l = left(num);
        int r = right(num);
        int smallest = num;
        if (l < size && array[l].key < array[smallest].key){
            smallest = l;
        }
        if (r < size && array[r].key < array[smallest].key){
            smallest = r;
        }
        if (smallest != num){
            swap(array, num, smallest);
            minHeapify(array, smallest);
        }
    }

    public void swap(Element[] array,int parent, int smallest){
        Element tmp= array[parent];
        array[parent] = array[smallest];
        array[smallest] = tmp;
    }

    public int heapSize(Element[] array){
        size = 0;
        for (int i = 0; i <array.length; i++) {
            if(array[i] != null){
                size++;
            }
        }
        return size;
    }

    @Override
    public void insert(Element e) {
        int i = 0;
        for (int j = 0; j <eList.length; j++) {
            if(eList[i]== null){
                eList[i] = e;
                break;
            }else{
                i++;
            }
        }
    }

    public int left(int i){
        return 2 * i+1;
    }

    public int right(int i){
        return 2 * i + 2;
    }
}

Element数组是必须具有的，因此没有注释，我应该使用arraylist。

当我运行代码时，结果如下：

3，
0，
1，
1，
1，
2，
-117，
3，
5，
100

这是测试类：

System.out.println();
System.out.println("Creating a PQHeap with room for 10 elements");
System.out.println();
    PQ pq = new PQHeap(10);

System.out.println("Inserting elements with keys");
System.out.println("  3, 5, 0, 100, -117, 1, 1, 1, 2, 3");
System.out.println("(and corresponding Integers as data)");
System.out.println();

pq.insert(new Element(3,new Integer(3)));
pq.insert(new Element(5,new Integer(5)));
pq.insert(new Element(0,new Integer(0)));
pq.insert(new Element(100,new Integer(100)));
pq.insert(new Element(-117,new Integer(-117)));
pq.insert(new Element(1,new Integer(1)));
pq.insert(new Element(1,new Integer(1)));
pq.insert(new Element(1,new Integer(1)));
pq.insert(new Element(2,new Integer(2)));
pq.insert(new Element(3,new Integer(3)));

System.out.println("Doing 10 extractMins (showing keys and data)");
System.out.println();
Element e;
for (int i=0; i<10; i++){
    e = pq.extractMin();
    System.out.println(e.key + " " + e.data);

非约翰

我解决了这个问题，不知道我应该删除帖子还是顺其自然，但这是解决方案。insert方法未遵循minHeap结构：

public void insert(Element e) {
    size = heapSize(eList);
    eList[size] = e;
    decreaseKey(eList, size, e.key);
}

public void decreaseKey(Element[] array, int i, int key){
    array[i].key = key;
    while (i > 0 && array[parent(i)].key > array[i].key){
        swap(array,i,parent(i));
        i = parent(i);
    }
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。