java implement heap operation method of build heap insert delete
- 2020-12-09 00:53:54
- OfStack
As shown below:
import java.util.Arrays;
// Small top heap code implementation
public class Heap {
// Adjust downward, the top of the large value down, mainly used to delete and build heap ,i Represents the node index to be adjusted, n Represents the most of the heap 1 Element index
// When I delete it, i is 0 When you build a pile i From the last 1 The parent of each node is adjusted forward in turn
public static void fixDown(int[] data, int i, int n) {
int num = data[i];
int son = i * 2 + 1;
while (son <= n) {
if (son + 1 <= n && data[son + 1] < data[son])
son++;
if (num < data[son])
break;
data[i] = data[son];
i = son;
son = i * 2 + 1;
}
data[i] = num;
}
// Adjust up, small value go up , Used to increase , You don't need to set the top index to move up, of course 0
public static void fixUp(int[] data, int n) {
int num = data[n];
int father = (n - 1) / 2;
// data[father] > num Is the basic condition for entering the loop ,father Reduced to 0 It's not going to go down
// when n Is equal to the 0 When, father=0 ; It goes into an infinite loop, so when n==0 , you need to get out of the loop
while (data[father] > num && n != 0) {
data[n] = data[father];
n = father;
father = (n - 1) / 2;
}
data[n] = num;
}
// delete ,n Represents the end of the heap 1 The index of the elements
public static void delete(int[] data, int n) {
data[0] = data[n];
data[n] = -1;
fixDown(data, 0, n - 1);
}
// increase ,i Represents the number to increase, n Represents the index of the added location, which is at the end of the heap 1 An element
public static void insert(int[] data, int num, int n) {
data[n] = num;
fixUp(data, n);
}
// Building the heap ,n Represents the end of the heap to be built 1 The index of the elements
public static void creat(int[] data, int n) {
for (int i = (n - 1) / 2; i >= 0; i--)
fixDown(data, i, n);
}
public static void main(String[] args) {
int[] data = { 15, 13, 1, 5, 20, 12, 8, 9, 11 };
// Test pile of building
creat(data, data.length - 1);
System.out.println(Arrays.toString(data));
// Test to delete
delete(data, data.length - 1);
delete(data, data.length - 2);
System.out.println(Arrays.toString(data));
// Test insert
insert(data, 3, data.length - 2);
System.out.println(Arrays.toString(data));
}
}