0
堆排序的下述方案：對空中交通的情況
一個小機場的管理已簽約你開發一個簡單的空中交通管制系統。該系統將允許機場控制塔內的空中交通管制員增加起飛和/或着陸的航班。每個航班都將被空中交通管制分配一個優先權。該系統將進一步保持一個單獨的起飛和着陸航班清單，並允許優先航班起飛或首先着陸。你的任務是選擇一個合適的數據結構來實現上述系統。您還必須證明系統正常工作。
講師告訴我們使用堆排序。因此，在規定的教科書，我覺得這個例子中（使用NetBeans應用）：
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();
}
}
我的問題是，我將如何調整下面的代碼給定的情景。
我想我可以創建第二個數組列表並聲明兩個已打開的布爾變量，並將必要的代碼應用於數組列表/對象，但仍然不知道如何編寫方法分配優先起飛/着陸。