我有一个程序,可以从一个文件中读取国家及其国内生产总值的列表,并将它们插入到MinHeap中。堆是国家对象的集合(数组)。国家对象具有两个字段。一个名为name的字符串字段,用于存储gdp值,该字段包含一个国家的两个字母代码和一个名为GDP的整数字段。insert方法使用GDP值作为插入键。由于这是一个MinHeap,国内生产总值最低的国家将永远是根源。此外,每次插入和删除堆后,都应该满足堆的所有其他属性。输入文件中不会有任何重复的GDP值。
我必须完成Heap.java类来实现以下功能:
removeMinGDP();应将国内生产总值最低的国家从堆中移出并归还。移除后,应还原堆属性。如果堆为空,则返回null。
removeGivenGDP(int ):应该找到具有给定GDP值的国家并将其移除。移除后,应还原堆属性。此函数应返回被删除的国家的名称。如果找不到具有给定GDP值的国家,则返回一个空字符串。
我需要一些关于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);
}
}
}发布于 2020-03-27 00:19:37
要删除给定的国内生产总值,你必须:
location.
storage数组中搜索包含请求值的条目。如果新值(从上一个节点复制的值)小于其父节点,则
storage。
是的,最后一个节点肯定比您删除的节点的父节点要小。有关示例,请参见https://stackoverflow.com/a/8706363/56778。
发布于 2020-03-26 23:37:18
deleteMin和downheap不需要Country arr[]或int n参数。它们应该直接操作storage和size实例变量:
private Country deleteMin(){
int last = storage[size-1];
Country temp = storage[0];
storage[0] = last;
...类封装状态: Heap类中的方法可以直接处理低级实现细节,比如“存储”数组。
https://stackoverflow.com/questions/60877235
复制相似问题