用java对象实现堆排序 [英] Implementing Heap Sort with java objects
本文介绍了用java对象实现堆排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我的任务是使用 java 实现堆排序.排序将按年薪进行，但对象员工将接受名称字符串和工资整数.我已经成功地使用基本相同的类进行冒泡排序，但是我在堆排序方面遇到了一些问题.这是我的代码:
I have been given the task of implementing a heap sort using java. The sorting will be by the annual salary but the object employee will accept both a string for name and an int for salary. I have been successful with bubblesort with basically the same classes but I am having some trouble with the heap sort. Here is my code:
import java.util.ArrayList;
import java.util.Scanner;
public class Company {
//create a default heap using array list
private ArrayList<Employee> list = new ArrayList<Employee>();
/* Add a new object into the binary heap */
//building a heap
public void addEmployee(Employee employee) {
list.add(employee); //append to the heap
}
public Employee remove() {
int count = 0;
if (list.isEmpty())
return null;
Employee 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 the 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;
count++;
}
}
// swap if the current node is less than the maximum
if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
Employee temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = maxIndex;
count++;
}
else
break;
}
// This is what I changed.
//list.add(0, removedObject);
//count++;
System.out.println(count);
return removedObject;
}
/*
* Method to print all elements in the ArrayList
*/
public void listEmployees(){
for (Employee employee : list)
System.out.println(employee.toString());
System.out.println();
}
public void listEmployeesSorted() {
ArrayList<Employee> copy = new ArrayList<Employee>(list);
StringBuilder builder = new StringBuilder();
while (list.size()>0) {
Employee e = this.remove();
builder.append(e.toString()+"\n");
}
this.list = copy;
System.out.println(builder.toString());
}
public static void main(String[] args) {
/*
* Instantiate object and call it 'direct'
*/
Company direct = new Company();
Scanner input=new Scanner(System.in);//Scanner Declaration
String name;
int salary;
/*
* Enter all the employee data
*/
direct.addEmployee(new EmployeeImp("John Hughes",36100));
direct.addEmployee(new EmployeeImp("Stephen Hughes",22100));
direct.addEmployee(new EmployeeImp("Michael Smith", 0));
direct.addEmployee(new EmployeeImp("Ludmilia Petrushevskaya", 120120));
direct.addEmployee(new EmployeeImp("Amy Gu", 36100));
direct.addEmployee(new EmployeeImp("Marta Villanueva Cortez", 34020));
direct.addEmployee(new EmployeeImp("Ian Palmer-Jones", 23090));
direct.addEmployee(new EmployeeImp("Andrew Andrews", 220100));
direct.addEmployee(new EmployeeImp("Andy Rainsford", 67000));
direct.addEmployee(new EmployeeImp("Bob Bobsworth", 23000));
direct.addEmployee(new EmployeeImp("Paul Smith", 29000));
direct.addEmployee(new EmployeeImp("James James", 23023));
direct.addEmployee(new EmployeeImp("Henry Cooper", 33900));
direct.addEmployee(new EmployeeImp("Ian Paisley", 33901));
direct.addEmployee(new EmployeeImp("Alan Ball", 45000));
direct.addEmployee(new EmployeeImp("Mick Channon", 55600));
direct.addEmployee(new EmployeeImp("Paul Halibut", 26780));
direct.addEmployee(new EmployeeImp("Raj Patel", 33090));
direct.addEmployee(new EmployeeImp("Mary James", 23000));
direct.addEmployee(new EmployeeImp("Alison Frogget", 78100));
direct.addEmployee(new EmployeeImp("Jenny Eclair", 40000));
direct.addEmployee(new EmployeeImp("Sasha Lane", 21000));
direct.addEmployee(new EmployeeImp("Sarah Milligan", 100300));
direct.addEmployee(new EmployeeImp("Zico", 120000));
direct.addEmployee(new EmployeeImp("Pippa Forester", 90000));
direct.addEmployee(new EmployeeImp("Angela Landsdowne", 8000));
direct.addEmployee(new EmployeeImp("Emily Taxem", -1000));
direct.addEmployee(new EmployeeImp("Jill Beans", 654000));
direct.addEmployee(new EmployeeImp("Alan Salt", 33333));
direct.addEmployee(new EmployeeImp("Imran Khan", 87000));
direct.addEmployee(new EmployeeImp("Matt Demon", 66666));
direct.addEmployee(new EmployeeImp("Douglas Adams", 42000));
System.out.println("\tName\t\t Salary");
direct.listEmployees();//print out all elements in ArrayList before sorting
System.out.println("\tName\t\t Salary");
System.out.println("__________________________________________________");
direct.listEmployeesSorted();//print out all elements in ArrayList after sorting
/*
* Use scanner to get user input (name,salary) to be entered into
* the existing sorted list
*/
System.out.print("Please enter a new employee's name: ");
name=input.nextLine();
System.out.print("Please enter the employee's associated salary: ");
salary=input.nextInt();
direct.addEmployee(new EmployeeImp(name,salary));
direct.listEmployeesSorted();
}//end main
}//end class Company
对于少量数据，它排序得很好，但是当我开始添加负数或 0 甚至有时只是正常的正值时，整个排序变得疯狂.我想知道是否有人可以帮我解决这个问题.我知道事实上是我的堆排序方法的实现导致了问题，其他一切都应该没问题...大声笑...请协助
For a small number of data it sorts well, but when i start adding negative numbers or 0 or even sometimes just normal positive values the whole sort gets crazy. I was wondering if anyone could help me fix this. I know for a fact it is the implementation of my heap sort methods that is giving the problem, everything else should be fine...lol...please assist
这是雇员类:
public abstract class Employee implements Comparable<Employee>{
private String name;
private int salary;
/*
* Two-Arguement Constructor
*/
Employee(String name, int salary){
this.name = name;
this.salary = salary;
}//end method
public int getSalary(){
return salary;
}//end method
/*
* Return the employee's name
*/
public String getName(){
return name;
}//end method
/*
* Return the compareTo
*/
public int compareTo(Employee x){
if (this.salary < x.salary)
return -1;
else if (this.salary > x.salary)
return 1;
else
return 0;
}//end method
public String toString(){
StringBuffer buffer = new StringBuffer();
buffer.append("\t");
buffer.append(getName());
buffer.append("\t ");
buffer.append(getSalary());
buffer.append("\t ");
return buffer.toString();
}
}
这是实现employee的子类:
and this is the sub class that implements employee:
class EmployeeImp extends Employee{
EmployeeImp(String name, int salary) {
super(name, salary);
}
}
推荐答案
我相信这是你的问题；你为什么在删除结束时这样做?
I believe this is your problem; why are you doing this at the end of remove?
list.add(0, removedObject);
count++;
是否应该删除?
//list.add(0, removedObject);
//count++;
我已经对您的代码的本地副本进行了上述更改(将 Employee 更改为非抽象)，并且它似乎工作正常.我使用下面的验证代码来检查随机数据.
I've made the change above on a local copy of your code (changed Employee to not be abstract) and it seems to be working fine. I've used this validatino code below to check using random data.
public boolean validate() {
Employee p = this.remove();
while (list.size()>0) {
Employee e = this.remove();
if (e.compareTo(p)>0) return false;
p = e;
}
return true;
}
测试代码.
boolean result = false;
for (int x=0; x<100; x++) {
int size = 100000;
for (int i=0; i<size; i++) {
int r = RANDOM.nextInt();
company.addEmployee(new Employee(String.valueOf(r),r));
}
result = company.validate();
if (result==false) break;
}
System.out.println(result);
这里是完整的删除方法:
Here is the full remove method:
public Employee remove() {
int count = 0;
if (list.isEmpty())
return null;
Employee 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 the 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;
count++;
}
}
// swap if the current node is less than the maximum
if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
Employee temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = maxIndex;
count++;
}
else
break;
}
// This is what I changed.
//list.add(0, removedObject);
//count++;
System.out.println(count);
return removedObject;
}
示例数据...请记住，(最大)堆的唯一保证是顶部元素将是堆中的最大值，并且每个父元素都将大于或等于它的子元素.
Example data... Remember, the only guarantee a (max) heap makes is the the top element will be the max in the heap AND every parent will be greater or equal to it's children.
Input order: 5, 12, 12, 17, 8, 7, 4, 1, 5, 19,
Companies internal list order: 19=19, 17=17, 12=12, 5=5, 12=12, 7=7, 4=4, 1=1, 5=5, 8=8,
Heap sorted order: 19=19, 17=17, 12=12, 12=12, 8=8, 7=7, 5=5, 5=5, 4=4, 1=1,
Company 的非破坏性打印方法(实际上是破坏性的，但在完成打印后返回初始状态):
A non destructive print method for Company (it's actually destructive but returns the initial state after it's done printing):
public String toString() {
ArrayList<Employee> copy = new ArrayList<Employee>(list);
StringBuilder builder = new StringBuilder();
while (list.size()>0) {
Employee e = this.remove();
builder.append(e.toString()+"\n");
}
this.list = copy;
return builder.toString();
}
这篇关于用java对象实现堆排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
