다음 시나리오가 제공됩니다.항공 교통 시나리오의 힙 정렬
간단한 비행장 관리는 간단한 항공 교통 제어 시스템을 개발하도록 계약했습니다. 이 시스템은 비행장 통제 탑에있는 항공 교통 통제가 이륙 및/또는 착륙을위한 항공편을 추가 할 수 있도록합니다. 각 항공편은 항공 교통 통제에 우선권을 부여받습니다. 시스템은 이륙 및 착륙을위한 별도의 항공편 목록을 유지 관리 할뿐만 아니라 우선 순위가 높은 항공편이 먼저 착륙하거나 착륙 할 수있게합니다. 당신의 임무는 위의 시스템을 구현하기위한 적절한 데이터 구조를 선택하는 것입니다. 시스템 작동 여부를 입증해야합니다.
강사는 힙 정렬을 사용하도록 알려줍니다. 그래서이 예제를 찾을 규정 된 교과서 (넷빈즈를 사용하여 적용) :
public class AirTraffic <E extends Comparable> {
private java.util.ArrayList<E>list = new java.util.ArrayList<E>();
/**
* Create a default heap
*/
public void heap()
{
}
/**
* Create a heap from an array of objects
*/
public void heap(E[]objects)
{
for (int i = 0; i < objects.length; i++)
{
add(objects[i]);
}
}
/**
* Add a new object into the heap
*/
public void add(E newObject)
{
list.add(newObject); //append to the heap
int currentIndex = list.size() - 1; //the index of the last node
while (currentIndex > 0)
{
int parentIndex = (currentIndex - 1)/2;
//swop if the current object is greater than its parent
if (list.get(currentIndex).compareTo(list.get(parentIndex)) > 0)
{
E temp = list.get(currentIndex); list.set(currentIndex, list.get(parentIndex)); list.set(parentIndex, temp);
} else {
break; //the tree is a heap now
}
currentIndex = parentIndex;
}
}
/**
* Remove the root from the heap
*/
public E remove()
{
if (list.size() == 0)
{
return null;
}
E removedObject = list.get(0); list.set(0, list.get(list.size() - 1)); list.remove(list.size() - 1);
int currentIndex = 0;
while (currentIndex < list.size())
{
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
//find the maximum between two children
if (leftChildIndex >= list.size())
{
break; //the tree is a heap
}
int maxIndex = leftChildIndex;
if (rightChildIndex < list.size())
{
if (list.get(maxIndex).compareTo(list.get(rightChildIndex)) < 0)
{
maxIndex = rightChildIndex;
}
}
//swop if the current node is less than the maximum
if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0)
{
E temp = list.get(maxIndex); list.set(maxIndex, list.get(currentIndex)); list.set(currentIndex, temp);
currentIndex = maxIndex;
} else {
break; //the tree is a heap
}
}
return removedObject;
}
/**
* Sort the values in the heap by repeatedly
* removing the root */
public void heapSort()
{
while (this.getSize() > 0)
{
System.out.print(this.remove().toString()+", "); }
}
/**
* Get the number of nodes in the tree
* @return
*/
public int getSize()
{
return list.size();
}
public static void main(String []args)
{
AirTraffic myHeap = new AirTraffic();
myHeap.add(20);
myHeap.add(6);
myHeap.add(78);
myHeap.add(40);
myHeap.add(5);
myHeap.heapSort();
System.out.println();
}
}
내 문제는 내가 주어진 시나리오에 다음 코드를 조정하는 방법입니다.
나는 두 번째 배열 목록을 만들고 배열 목록/개체에 필요한 코드를 적용하는 두 개의 부울 변수를 선언 할 수 있다고 생각했지만 여전히 어떻게 코드를 작성해야할지 모르겠다. 우선 순위는 이륙/착륙을 지정하십시오.