Heap sort with java


  • 0
    W
      public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int a[] = new int[nums.length + 1];
        a[0] = 1<<20;
        for(int i = 0; i < nums.length; i++ ){
            insert(a, nums[i], i);
        }
        int result = 0;
        int i = 0;
        for(i = 0; i < k; i++){
            result = deletemax(a, nums.length - i);
        }
        return result;
    }
    public void insert(int a[], int key, int size){
        int i = 0;
        for(i = ++size ; i >= 0; i = i/2 ){//设置哨兵,a[0]
            if(a[i/2] < key){
                a[i] = a[i/2];
            }
            else{
                break;
            }
        }
        a[i] = key;
        
    }
    public int deletemax(int a[], int Size){
        int left = 1;
        int max = a[1];
        int i = 0;
        int last = a[Size--];//size同时减一,一定要减一
        for(i = 1; i * 2 <= Size; i = left){
            left = 2*i;
            if(left != Size &&a[left] < a[left + 1] ){//letf != Size, 一定不能少因为最后一个可能没有右孩子,注意测试顺序
                left++;
            }
            if(last < a[left]){
                a[i] = a[left];
            }
            else{
                break;
            }
        }
        a[i] = last;
        return max;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.