package my;import java.util.ArrayList;;public class Heap {
private ArrayList<Integer> array = new ArrayList<Integer>(); int size = array.size(); public Heap(ArrayList<Integer> array) {
this.array = array;
} public int parent(int i) {
return (i - 1) / 2;
} public int left(int i) {
return 2 * i;
} public int right(int i) {
return 2 * i + 1;
} public void swap(int i, int j) {
int iValue = array.get(i);
int jValue = array.get(j);
array.set(i, jValue);
array.set(j, iValue);
} public void max_heapify(int i) {
int large = 0;
int l = left(i);
int r = right(i);
if (l <= size && array.get(l) > array.get(i))
large = l;
else
large = i; if (r <= size && array.get(r) > array.get(large))
large = r; if (large != i)
swap(i, large); max_heapify(large);
} public void build_max_heap() {
for (int i = parent(size - 1); i > 0; i--)
max_heapify(i);
} public void sort() {
build_max_heap();
for (int i = size; i >= 2; i--) {
swap(1, i);
size--;
max_heapify(1);
}
} public static void main(String[] args) {
ArrayList<Integer> array1 = new ArrayList<Integer>();
//for (int i = 0; i <10; i++)
// array1.add(i);
array1.add(2);
array1.add(22);
array1.add(13);
array1.add(56);
array1.add(44);
Heap h = new Heap(array1);
h.sort();
for (int i = 0; i < 5; i++)
System.out.print(array1.get(i) + " "); }
}本来应该输出56 44 22 13 2的,但是现在的输出却是2 22 13 56 44
private ArrayList<Integer> array = new ArrayList<Integer>(); int size = array.size(); public Heap(ArrayList<Integer> array) {
this.array = array;
} public int parent(int i) {
return (i - 1) / 2;
} public int left(int i) {
return 2 * i;
} public int right(int i) {
return 2 * i + 1;
} public void swap(int i, int j) {
int iValue = array.get(i);
int jValue = array.get(j);
array.set(i, jValue);
array.set(j, iValue);
} public void max_heapify(int i) {
int large = 0;
int l = left(i);
int r = right(i);
if (l <= size && array.get(l) > array.get(i))
large = l;
else
large = i; if (r <= size && array.get(r) > array.get(large))
large = r; if (large != i)
swap(i, large); max_heapify(large);
} public void build_max_heap() {
for (int i = parent(size - 1); i > 0; i--)
max_heapify(i);
} public void sort() {
build_max_heap();
for (int i = size; i >= 2; i--) {
swap(1, i);
size--;
max_heapify(1);
}
} public static void main(String[] args) {
ArrayList<Integer> array1 = new ArrayList<Integer>();
//for (int i = 0; i <10; i++)
// array1.add(i);
array1.add(2);
array1.add(22);
array1.add(13);
array1.add(56);
array1.add(44);
Heap h = new Heap(array1);
h.sort();
for (int i = 0; i < 5; i++)
System.out.print(array1.get(i) + " "); }
}本来应该输出56 44 22 13 2的,但是现在的输出却是2 22 13 56 44
private ArrayList<Integer> array = new ArrayList<Integer>(); int size = array.size(); public Heap(ArrayList<Integer> array) {
this.array = array;
} public int parent(int i) {
return (i - 1) / 2;
} public int left(int i) {
return 2 * i;
} public int right(int i) {
return 2 * i + 1;
} public void swap(int i, int j) {
int iValue = array.get(i);
int jValue = array.get(j);
array.set(i, jValue);
array.set(j, iValue);
} public void max_heapify(int i) {
int large = 0;
int l = left(i);
int r = right(i);
if (l < size && array.get(l) > array.get(i))
large = l;
else
large = i; if (r < size && array.get(r) > array.get(large))
large = r; if (large != i) {
swap(i, large);
max_heapify(large);
}
} public void build_max_heap() {
for (int i = parent(size - 1); i >= 0; i--)
max_heapify(i);
} public void sort() {
build_max_heap();
for (int i = size - 1; i > 0; i--) {
swap(0, i);
size--;
max_heapify(0);
}
}
public static void main(String[] args) {
ArrayList<Integer> array1 = new ArrayList<Integer>();
// for (int i = 0; i <10; i++)
// array1.add(i);
array1.add(2);
array1.add(22);
array1.add(13);
array1.add(56);
array1.add(44);
Heap h = new Heap(array1);
h.sort(); }
}
private ArrayList<Integer> array; int size; public Heap(ArrayList<Integer> array,int size) {
this.array = array;
this.size = size;
} public int parent(int i) {
return (i - 1) / 2;
} public int left(int i) {
return 2 * i;
} public int right(int i) {
return 2 * i + 1;
} public void swap(int i, int j) {
int iValue = array.get(i);
int jValue = array.get(j);
array.set(i, jValue);
array.set(j, iValue);
} public void max_heapify(int i) {
int large = 0;
int l = left(i);
int r = right(i);
if (l < size && array.get(l) > array.get(i))
large = l;
else
large = i; if (r < size && array.get(r) > array.get(large))
large = r; if (large != i) {
swap(i, large);
max_heapify(large);
}
} public void build_max_heap() {
for (int i = parent(size - 1); i >= 0; i--)
max_heapify(i);
} public void sort() {
// build_max_heap();
for (int i = size - 1; i > 0; i--) {
swap(0, i);
size--;
max_heapify(0);
}
} public void show() {
for (int i = 0; i < array.size(); i++)
System.out.print(array.get(i) + " ");
} public static void main(String[] args) {
ArrayList<Integer> array1 = new ArrayList<Integer>();
// for (int i = 0; i <10; i++)
// array1.add(i);
array1.add(2);
array1.add(22);
array1.add(13);
array1.add(56);
array1.add(44);
Heap h = new Heap(array1,5);
h.build_max_heap();
h.sort();
h.show(); }
}这样可以输出2 13 22 44 56