Implementation of the underlying structure of heap in Java

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[1];
        // 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[1] = 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 .