nerohoop

0x16f1D1013DA57B6552a6Ee04Ec0706DD011B2Aca

nerohoop

1. Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time
2. One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.

nerohoop

void Sort::insertionSort(int *arr, int size) {
    int key = 0;
    for (int i=1; i < size; i++) {
        key = arr[i];
        
        // Move elements of arr[0..i-1], that are greater than key,
        // to one position ahead of their current position.
        int j = i-1;
        while (j>=0 && arr[j] > key) {
            arr[j+1] = arr[j];

nerohoop

bool BinaryHeap::isArrayHeap(int *arr, int size) {
    for (int i=0; i<size/2; i++) {
        if(2*i+1 < size && arr[2*i+1] > arr[i]) return false;
        if(2*i+2 < size && arr[2*i+2] > arr[i]) return false;
    }
    
    return true;
}

nerohoop

bool BinaryHeap::isArrayHeap(int *arr, int size) {
    for (int i=0; i<(size-2)/2; i++) {
        if(2* arr[2*i+1] > arr[i]) return false;
        if(arr[2*i+2] > arr[i]) return false;
    }
    
    return true;
}

nerohoop

// This function checks if the binary tree is complete or not
bool BinaryTree::isCompleteUtil(Node *root, int index, int size) {
    // An empty tree is complete
    if (!root) return true;
    
    // If index assigned to current node is more than
    // number of nodes in tree, then tree is not complete
    if (index >= size) return false;
    
    // Recur for left and right subtrees

nerohoop

1. Build a max heap from the input data.
2. Replace the root with the last item of the heap followed by reducing the size by 1.
3. Heapify the root of tree.
4. Repeat above steps while size of heap is greater than 1.

nerohoop

Build_Heap(A) 
    heapsize := size(A); 
    for i := floor(heapsize/2) downto 1 
        do Heapify(A, i); 
    end for 
End

nerohoop

The root element will be at Arr[0]. 
Below table shows indexes of other nodes for the ith node, i.e., Arr[i]:
Arr[i/2]     Returns the parent node
Arr[(2*i)+1] Returns the left child node
Arr[(2*i)+2] Returns the right child node

nerohoop

Node* BinarySearchTree::deleteKey(Node *root, int key) {
    if (!root) return root;
    
    if (key < root->val) {
        // If the key to be deleted is smaller than the root's key, then it lies in left subtree
        root->left = deleteKey(root->left, key);
    } else if (key > root->val) {
        // If the key to be deleted is greater than the root's key, then it lies in right subtree
        root->right = deleteKey(root->right, key);
    } else {