具有 2 个字段的 MinHeap...removeMin 并删除给定的键

Question

我有一个程序可以从文件中读取国家列表及其 GDP，并将它们插入到 MinHeap 中。堆是 Country 对象的集合（数组）。一个 Country 对象有两个字段。一个名为 name 的字符串字段，其中包含一个国家的两个字母代码和一个名为 gdp 的整数字段，用于存储 GDP 值。插入方法使用 GDP 值作为插入键。由于这是一个 MinHeap，因此 GDP 最低的国家总是处于根部。此外，堆的所有其他属性都应在每次插入和移除后得到满足。输入文件中不会有任何重复的 GDP 值。

我必须完成 Heap.java class 才能实现以下功能：

removeMinGDP();应该从堆中删除 GDP 最低的国家和 return 它。删除后，堆属性应该会恢复。 return 如果堆为空则为 null。

removeGivenGDP(int gdp)：应该找到具有给定 GDP 值的国家并将其删除。删除后，堆属性应该会恢复。此函数应该 return 被删除的国家名称。如果找不到具有给定 GDP 值的国家/地区，return 一个空字符串。

我需要一些有关 removeMinGDP 的帮助。我知道我将删除根并将其替换为最大的元素。我知道我必须下山。我知道大致的想法，但不确定如何执行。所以基本上我被卡住了，因为 removeMinGDP 不接受参数所以我不得不创建两个私有方法，但我不知道要传递给 deleteMin。

我知道我还没有开始使用 removeGivenGDP（但很乐意接受帮助）。而且我的编码经验很少，所以请不要把我活活吃掉。


  private Country[] storage; //the actual heap storing elements
  private int size; //number of elements currently in the heap
  private int cap; //capacity of the heap

  Heap (int c) {
    size = 0;
    cap = c;
    storage = new Country[cap];
  }

  public void insert(Country c) {
    if (size >= cap) {
      throw new IllegalStateException("Heap is full");
    }
    int curr = size++;
    storage[curr] = c;
    while ((curr != 0) && (storage[curr].gdp < storage[parent(curr)].gdp)) {
      exch(storage, curr, parent(curr));
      curr = parent(curr);
    }

  }

  private void exch(Country[] arr, int i, int j) {
    Country tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

  private int parent(int i) {
    if (i <= 0) return -1;
    return (i-1)/2;
  }

  public int numCountries () {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  private boolean isLeaf(int pos)
  { 
    return (pos >= size/2) && (pos < size); 

  }

  private int leftchild(int pos) {
    if (pos >= size/2) return -1;
    return 2*pos + 1;
  }


  private int rightchild(int pos) {
    if (pos >= (size-1)/2) return -1;
    return 2*pos + 2;
  }

//***************************************************************************

  public Country removeMinGDP() {
    /**************************
     * remove the country with minimum  GDP
     * from the heap and return it. restore
     * the heap properties.
     * return null if heap is empty.
    ***************************/
    if(isEmpty()) return null;
    else{
      return deleteMin(arr,size);
  }
  }

  private Country deleteMin(Country arr[], int n){
    int last = arr[n-1];
    Country temp = arr[0];
    arr[0] = last;
    n = n-1;
    downheap(arr,n,0);
    return temp.name;
  }

  private void downheap(Country arr[], int n, int i){
    int biggest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if(l < n && arr[l].gdp > arr[biggest].gdp) biggest = l;
    if(r < n && arr[r].gdp > arr[biggest].gdp) biggest = r;
    if(biggest != i){
      int swap = arr[i];
      arr[i] = arr[biggest];
      arr[biggest] = swap;

      downheap(arr, n, biggest);
    }
  }


  public String removeGivenGDP(int gdp) {
    /**************************
     * TODO: find the country with the given GDP 
     * value and remove it. return the name of 
     * the country and restore the heap property
     * if needed. If no countries with the given GDP
     * were found, return empty string ""
    ***************************/
    return "";
  }
}

这是主要功能。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

class Main {
  public static void main(String[] args) throws FileNotFoundException {
    File input = new File("countries.txt");

    //Creating Scanner instance to read File
    Scanner sc = new Scanner(input);

    //Create an instance of MinHeap
    Heap h = new Heap(10);

    //Reading each line of file using Scanner class
    while(sc.hasNextLine()){
        String[] tokens = sc.nextLine().split(",");
        System.out.println("Inserted: " + tokens[0] + " -> " + tokens[1]);
        h.insert(new Country(tokens[0], Integer.parseInt(tokens[1].trim())));
    }

    System.out.println("\n\nTotal number of countries inserted is: " + h.numCountries());
    System.out.println("The name of the country with a GDP value of 2314 is " + h.removeGivenGDP(2314));
    System.out.println("Total number of countries now is: " + h.numCountries());

    System.out.println("\n\nCountries in ascending order of GDP values: ");
    while (!h.isEmpty()) {
      Country tmp = h.removeMinGDP();
      System.out.println(tmp.name + " -> " + tmp.gdp);
    } 

  }
}

Answer 1

deleteMin 和 downheap 不需要 Country arr[] 或 int n 参数。它们应该直接对 storage 和 size 实例变量进行操作：

  private Country deleteMin(){
    int last = storage[size-1];
    Country temp = storage[0];
    storage[0] = last;
    ...

A class encapsulates 状态：堆中的方法 class 可以直接使用低级实现细节，例如 "storage" 数组.

Answer 2

要删除给定的 GDP，您必须：

在 storage 数组中搜索包含请求值的条目。
将堆中的最后一个节点复制到该位置。
将大小减小 1。
如果新值（您从最后一个节点复制的值）小于其父节点，则您需要在堆中向上筛选该节点。否则，您需要将其从堆中筛选到适当的位置。

是的，最后一个节点肯定可以小于您删除的节点的父节点。有关示例，请参阅。

具有 2 个字段的 MinHeap...removeMin 并删除给定的键

MinHeap with 2 fields... removeMin and remove given key

java

heap

min-heap