最小堆实现

清疚 2024-02-18 20:24 60阅读 0赞

### 题目 ###

最小堆实现

### 解答 ###

public class MinHeap {
        
    
        public static void main(String[] args) {
            int[] test = {
       23,42,5,1,56};
            heapify(test);
            print(0,test);
        }
    
    
        public static void print(int index,int[] tests){
    
            System.out.println(tests[getLeft(index)]);
            System.out.println(tests[index]);
            System.out.println(tests[getRight(index)]);
    
        }
        /*
         * @param A: Given an integer array
         * @return: nothing
         */
        public static void heapify(int[] A) {
            // write your code here
            for (int i = A.length/2-1;i>=0; i--) {
                change(i, A.length, A);
            }
        }
    
        public static void change(int index, int length, int[] temp) {
            int smallest = index;
            int left = getLeft(index);
            int right = getRight(index);
    
            if (left < length && temp[left] < temp[smallest]) {
                smallest = left;
            }
    
            if (right < length && temp[right] < temp[smallest]) {
                smallest = right;
            }
            // 左右结点的值都大于根节点，直接return，不做任何操作
            if (index == smallest) {
                return;
            }
            swap(index, smallest, temp);
            change(smallest, length, temp);
        }
    
        public  static void swap(int index, int smallest, int[] temp) {
            int curr = temp[index];
            temp[index] = temp[smallest];
            temp[smallest] = curr;
        }
    
        public static int getLeft(int index) {
            return index * 2 + 1;
        }
    
        public  static int getRight(int index) {
            return index * 2 + 2;
        }
    }