Solution via MaxHeap in C and Complexity Analysis


  • 2
    S
    #define PARENT(x) x  
    

    #define LCHILD(x) 2 * x + 1
    #define RCHILD(x) 2 * x + 2

    typedef struct node {

    int data ;
    

    } node ;

    typedef struct maxHeap {

    int size ;
    node *elem ;
    

    } maxHeap ;

    maxHeap initMinHeap(int size) {

    maxHeap hp ;
    hp.size = 0 ;
    return hp ;
    

    }

    void swap1(node *n1, node *n2) {

    node temp = *n1 ;
    *n1 = *n2 ;
    *n2 = temp ;
    

    }

    void heapify(maxHeap *hp, int i) {

    int largest = (LCHILD(i) < hp->size && hp->elem[LCHILD(i)].data > hp->elem[i].data) ? LCHILD(i) : i ;
    if(RCHILD(i) < hp->size && hp->elem[RCHILD(i)].data > hp->elem[largest].data) {
        largest = RCHILD(i) ;
    }
    if(largest != i) {
        swap1(&(hp->elem[i]), &(hp->elem[largest])) ;
        heapify(hp, largest) ;
    }
    

    }

    void buildMaxHeap(maxHeap *hp, int *arr, int size) {
    int i ;

    // Insertion into the heap without violating the shape property
    for(i = 0; i < size; i++) {
        if(hp->size) {
            hp->elem = (node*)realloc(hp->elem, (hp->size + 1) * sizeof(node)) ;
        } else {
            hp->elem =(node*) malloc(sizeof(node)) ;
        }
        node nd ;
        nd.data = arr[i] ;
        hp->elem[(hp->size)++] = nd ;
    }
    
    // Making sure that heap property is also satisfied
    for(i = (hp->size - 1) / 2; i >= 0; i--) {
        heapify(hp, i) ;
    }
    

    }

    int findKthLargest(int* nums, int numsSize, int k) {

    maxHeap hp=initMinHeap(numsSize);
    buildMaxHeap(&hp,nums,numsSize);
    for (int i = 0; i < k-1; i++) {
    			//cout<<"largest:"<<hp.elem[0].data<<endl;
    			swap1(&hp.elem[0], &hp.elem[hp.size-1]);
    			hp.size--;
    		    // Making sure that heap property is also satisfied
    		    for(int j = (hp.size - 1) / 2; j >= 0; j--) {
    		        heapify(&hp, j) ;
    		    }
            }
    return hp.elem[0].data;
    

    }

        Complexity Analysis :
        
        finding the largest element in a heap is O(1) 
        Heaplify Complexity O(logn) 
        Building of heap O(n)
    [Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).] 
        Extracting K elements from a heap, and returning the heap of non-extracted elements, would take O(K·log(N)) time.
    

    Thus overall Timecomplexity of this solution :
    O(n + klogn)


  • 0
    B

    your solution will not work in case of duplicate let suppose arr is 0 -1 0 and we want to extract
    3rd largest element so your solution will give 0 but ans should be -1


  • 0
    S

    @Brijesh :

    read the question , it says
    "Note that it is the kth largest element in the sorted order, not the kth distinct element."
    thanks


Log in to reply
 

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