# Implementation of the underlying structure of heap in Java

2022-01-27 00:55:35

### The characteristics of the heap ：

1、 It's a complete binary tree , Except for the last layer of the tree, nodes do not need to be full , Every other floor is full from left to right , If the last node is not It's full , Then ask left man right dissatisfaction . 2、 It's usually implemented in arrays , Put the nodes of the binary tree into the array in hierarchical order , Where is the root node 1, Its child nodes are in position 2 and 3, And the child of the child node The nodes are located at 4,5,6 and 7, And so on . If the index of a node in the array is k, Then the index of its parent node is k/2, The indexes of its left and right child nodes are 2k and 2k+1. such , Without using a pointer , We can move nodes up and down the tree by calculating the index of elements in the array

3、 The value of each node is greater than or equal to its two child nodes .

### Heaped API Design ### Heap code implementation

``````/**
* @author: xuzhilei6656
* @create: 2021-12-10 11:26
* @description:  The realization of the heap
**/
public class Heap<T extends Comparable<T>> {
// Store the elements in the heap
private final T[] items;
// Record the number of elements in the heap
private int number;

// Construction method
public Heap(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.number = 0;
}

// Determine the index in the heap i Whether the value at is less than the index j Place the value of the
public boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}

// In the swap heap i Index and j The value of the index
public void exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}

// Insert an element into the team
public void insert(T t){
// Add an element to the array
items[++number] = t;
// Element floating up
swim(number);
}
// Use the floating up algorithm , Make index k The element at can be in the correct position in the heap
private void swim(int k) {
while (k > 1){
// If k The value of the node is greater than the value of the parent node , The exchange
if (less(k/2,k)){
exch(k/2,k);
}
// Transformation k
k = k/2;
}
}

// Delete the largest element in the heap , And return the largest element
public T delMax(){
// The first element in the heap is the largest element
T max = items;
// Exchange index 1 Elements at and at the maximum index , Let the last element of the complete binary tree become a temporary root node
//items = items[number]; // This method is also feasible
exch(1,number);
// Delete the value at the maximum index
items[number] = null;
number--;
// Use sinking algorithm , Put the temporary root node in the right position
sink(1);
return max;
}
// Use sinking algorithm , Let index k The element at is in the right position
private void sink(int k) {
// Circular comparison index k The element size of the element and its left and right child nodes , Give Way k The element at the index is swapped with the larger one
while (2*k<=number){
// Record the index value of the larger element
int max;
// If there are right child nodes
if (2*k+1<=number){
// Compare the size of the left and right child node elements , Give the larger index to max
if (less(2*k,2*k+1)){
max = 2*k+1;
}else {
max = 2*k;
}
}else {
max = 2*k;
}

// Compare current index k Element and index at max Element size at
if (!less(k,max)){
break;
}
// Exchange index k And index max Element position at
exch(k,max);
// Transformation k Value
k = max;
}
}

// Get the number of elements in the heap
public int size(){
return number;
}

// Determine whether the heap is empty
public boolean isEmpty(){
return number==0;
}

public static void main(String[] args) {
Heap<String> heap = new Heap<>(20);
heap.insert("A");
heap.insert("B");
heap.insert("C");
heap.insert("D");
heap.insert("E");
heap.insert("F");
heap.insert("G");

String max;
while ((max = heap.delMax())!=null){
System.out.println(max);
}
}

}``````

test result The above is only for personal study demo, If there is something wrong , You can leave a message below to correct , thank you . With you CSDN Our partners encourage , Record a little every day , Make a little progress every day .