实现堆排序与Java对象 [英] Implementing Heap Sort with java objects
本文介绍了实现堆排序与Java对象的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我一直在考虑实施一个堆排序用java的任务。排序将是年薪，但对象员工都接受了这两个名称的字符串和薪水一个int。我已经成功用冒泡具有基本相同的类，但我有一些麻烦与堆排序。这里是我的code：
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();
}
}
这是实现员工的子类：
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++;
我做了上面你code的本地副本的改变（改变员工到不能是抽象的），它似乎是工作的罚款。我用低于这个validatino code。使用随机数据进行检查。
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;
}
测试code。
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,
有关公司A无损的打印方法（它实际上是破坏性的，但返回它的完成打印后，初始状态）：
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屋！
查看全文
