用堆求解最小可用ID问题

题目

在非负数组（乱序）中找到最小的可分配的id（从1开始编号）数据是1000000

分析

第一个最小值是1，第二个最小值是2，第三个最小值是4.那么最小可用ID是3.
可以用小顶堆求每次的最小值。

package com.company;

import com.company.util.ArrayUtil;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class Main {

    public static void main(String[] args) {
	    // write your code here
        int[] A={1,2,3,4,6,7,8,9,10};
//        int[] A=ArrayUtil.randomArray(-10,10,10);
        int len;
        len=A.length;
        heapify(A,len);
        int counter;
        int oldLen=A.length;
        for ( counter = 1; counter <=oldLen-1 ; counter++) {
            int min=A[0];
            if(min!=counter){
                System.out.println(counter);
                break;
            }
            ArrayUtil.swap(A,0,len-1);
            len--;
            heapify(A,len);



        }
        if(counter==oldLen){
            System.out.println(A[0]+1);
        }



    }
    public static void heapify(int[]A,int len){
        for (int i =len/2 ; i >=0 ; i--) {
            int left=2*i+1;
            int right=2*i+2;

            int min=i;
            if(left<len&&A[left]<A[i]){
                min=left;
            }
            if(right<len&&A[right]<A[i]){
                min=right;
            }

            if(min!=i){
                down(A,i,len);
            }


        }
        System.out.println(Arrays.toString(A));
    }
    private static void down(int[]heap,int parent,int len) {
        int size=len;
        int leftChild = parent*2 + 1;
        int rightChild = parent*2 + 2;
        int min = parent;
        if (leftChild < size && heap[min] > heap[leftChild]) {
            min = leftChild;
        }
        if (rightChild < size && heap[min] > heap[rightChild]) {
            min = rightChild;
        }
        if (min != parent) {
            ArrayUtil.swap(heap,min, parent);
            down(heap,min,size);
        }
    }








}