import java.util.*;

public class Checker {

    public boolean checkDuplicate(int[] a, int n) {

        int lastIndex = n - 1;

        builedMaxHeap(a,lastIndex);

        while(lastIndex > 0){

            swap(a,0,lastIndex);

            if(--lastIndex == 0){//如果只剩一个元素，就不用重新建堆了，排序结束

                break;

            }

            adjustHeap(a,0,lastIndex);

        }

        for(int i = 0; i < n-1; i++){

            if(a[i] == a[i+1])

                return true;

        }

        return false;

    }

    public void builedMaxHeap(int[] arr, int lastIndex) {

        //从最后一个元素的父元素开始构建最大堆

        int j = (lastIndex - 1)/2;

        while(j >= 0){

            int rootIndex = j;

            adjustHeap(arr,rootIndex,lastIndex);

            j--;

        }

    }

    public void adjustHeap(int[] arr, int rootIndex, int lastIndex) {

        int childNodeIndex = rootIndex * 2 + 1;

        while(childNodeIndex <= lastIndex){//至少有一个子节点的时候，继续循环

            //有右孩子，并且右孩子比左孩子大，那么childNodeIndex赋值给更大的孩子

            if((childNodeIndex+1) <= lastIndex && arr[childNodeIndex+1] > arr[childNodeIndex]){

                childNodeIndex++;

            }

            //子孩子比父亲小,说明堆构建完成,跳出循环

            if(arr[childNodeIndex] <= arr[rootIndex]){

                break;

            }

            else{

                swap(arr, rootIndex, childNodeIndex);

                rootIndex = childNodeIndex;

                childNodeIndex = childNodeIndex * 2 + 1;

            }

        }

    }

    public void swap(int[] arr, int m, int n) {

        int temp = arr[m];

        arr[m] = arr[n];

        arr[n] = temp;

    }

}