The Java language implements the largest code sample
- 2020-12-07 04:05:15
- OfStack
The maximum heap
The largest heap is characterized by the parent being larger than the child, and having a complete two-tree.
data[1] starts saving, data[0] is empty. You can also use data[0] as size.
public class MaxHeap<T extends Comparable<? super T>> {
private T[] data;
private int size;
private int capacity;
public MaxHeap(int capacity) {
this.data = (T[]) new Comparable[capacity + 1];
size = 0;
this.capacity = capacity;
}
public int size() {
return this.size;
}
public Boolean isEmpty() {
return size == 0;
}
public int getCapacity() {
return this.capacity;
}
/**
* @return View the maximum root ( Can't delete , with popMax contrast )
*/
public T seekMax() {
return data[1];
}
public void swap(int i, int j) {
if (i != j) {
T temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
public void insert(T item) {
size++;
data[size] = item;
shiftUp(size);
}
/**
* @return Maximum pop root ( Pop up means delete , with seekMax contrast )
*/
public T popMax() {
swap(1, size--);
shiftDown(1);
return data[size + 1];
}
/**
* @param child The child node subscript is child , the parent node is the lower corner table child/2
*/
public void shiftUp(int child) {
while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
swap(child, child / 2);
child = child / 2;
}
}
/**
* @param a data The subscript of an element in an array
* @param b data The subscript of an element in an array
* @return Returns the subscript of which element is larger
*/
private int max(int a, int b) {
if (data[a].compareTo(data[b]) < 0) {
// if data[b] big
return b;
// return b
} else {
// if data[a] big
return a;
// return a
}
}
/**
* @param a data The subscript of an element in an array
* @param b data The subscript of an element in an array
* @param c data The subscript of an element in an array
* @return Returns the subscript of which element is larger
*/
private int max(int a, int b, int c) {
int biggest = max(a, b);
biggest = max(biggest, c);
return biggest;
}
/**
* @param father The parent node subscript is father, The lower corner table of the left and right child nodes is as follows: father*2 and father*2+1
*/
public void shiftDown(int father) {
while (true) {
int lchild = father * 2;
// Left the child
int rchild = father * 2 + 1;
// The right child
int newFather = father;
//newFather About to update, father, left, right 3 Which node is bigger, newFather Whose subscript
if (lchild > size) {
// If the father The node has neither left nor right children
return;
} else if (rchild > size) {
// If the father Nodes have only left children, no right children
newFather = max(father, lchild);
} else {
// If the father The node has both left children and right children
newFather = max(father, lchild, rchild);
}
if (newFather == father) {
// instructions father It's bigger than the two children, and the table name is already a big root heap, so you don't have to adjust it any more
return;
} else {
// Otherwise, you need to continue tuning the heap until the large root heap condition is satisfied
swap(father, newFather);
// Exchange values
father = newFather;
// update father Is equivalent to continuing to adjust shiftDown(newFather)
}
}
}
public static void main(String[] args) {
// Create a large root heap
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
// To the heap
for (int i = 0; i < 100; i++) {
maxHeap.insert((int) (Math.random() * 100));
}
// Create an array
Integer[] arr = new Integer[100];
// Take it out of the heap, put it in the array
for (int i = 0; i < 100; i++) {
arr[i] = maxHeap.popMax();
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
The shiftDown() function is not the same as above
public class MaxHeap<T extends Comparable<? super T>> {
private T[] data;
private int size;
private int capacity;
public MaxHeap(int capacity) {
data = (T[]) new Comparable[capacity + 1];
this.capacity = capacity;
size = 0;
}
public int size() {
return size;
}
public Boolean isEmpty() {
return size == 0;
}
public void insert(T item) {
data[size + 1] = item;
size++;
shiftUp(size);
}
/**
* @return Maximum pop root ( Pop up means delete , with seekMax contrast )
*/
public T popMax() {
T ret = data[1];
swap(1, size);
size--;
shiftDown(1);
return ret;
}
/**
* @return View the maximum root ( Can't delete , with popMax contrast )
*/
public T seekMax() {
return data[1];
}
public void swap(int i, int j) {
if (i != j) {
T temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
public void shiftUp(int k) {
while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
swap(k, k / 2);
k /= 2;
}
}
public void shiftDown(int father) {
while (2 * father <= size) {
int newFather = 2 * father;
if (newFather + 1 <= size && data[newFather + 1].compareTo(data[newFather]) > 0) {
//data[j] data[j+1] Take the larger of the two
newFather = newFather + 1;
}
if (data[father].compareTo(data[newFather]) >= 0) {
break;
} else {
swap(father, newFather);
// Exchange values
father = newFather;
//newFather is (2*father) Or is it (2*father+1), Which is to go on shiftDown(newFather);
}
}
}
public static void main(String[] args) {
// Create a large root heap
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
// To the heap
for (int i = 0; i < 100; i++) {
maxHeap.insert((int) (Math.random() * 100));
}
// Create an array
Integer[] arr = new Integer[100];
// Take it out of the heap, put it in the array
for (int i = 0; i < 100; i++) {
arr[i] = maxHeap.popMax();
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
conclusion
That's it for the most extensive code examples of Java language implementations in this article, and I hope you found them helpful. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!