Heapify

Description

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i 2 + 1] is the left child of A[i] and A[i 2 + 2] is the right child of A[i].

Clarification:

What is heap?

• Heap is a data structure, which usually have three methods: push, pop and top. where "push" add a new element the heap, "pop" delete the minimum/maximum element in the heap, "top" return the minimum/maximum element.

What is heapify?

• Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i 2 + 1] >= A[i] and A[i 2 + 2] >= A[i].

What if there is a lot of solutions?

• Return any of them.

Example
Given [3,2,1,4,5], 
return [1,2,3,4,5] or any legal heap array.

Challenge:
O(n) time complexity

Link

Lintcode_ladder

Method

1. sift down: O(n)
2. sift up: O(nlogn)

Example

1. 1

class Solution {
public:
    /**
     * @param A: Given an integer array
     * @return: void
     */
    void heapify(vector<int> &nums) {
        // write your code here
        if (nums.empty()) {
            return;
        }
        int len = nums.size();
        // for (int i = len / 2; i >= 0; --i) {
        //     siftdown(nums, i);
        // }
        for (int i = 1; i < nums.size(); ++i) {
            siftup(nums, i);
        }
        return;
    }
private:
    // siftdown: check from father, if child > father, siftdown father
    // O(n), every entry has nearly only one access
    // Based on bottom child to top father, once bottom child is checked,
    //  thesre is no need to check again.
    void siftdown(vector<int>& nums, int k) {
        int len = nums.size();
        while (k < len) {
            int small = k;
            // find smallest value's index
            if (k * 2 + 1 < len && nums[k * 2 + 1] < nums[small]) {
                small = k * 2 + 1;
            }
            if (k * 2 + 2 < len && nums[k * 2 + 2] < nums[small]) {
                small = k * 2 + 2;
            }
            // if cannot find, break
            if (small == k) {
                break;
            }
            // if can find swap value
            swap(nums[k], nums[small]);
            // update small
            k = small;
        }
        return;
    }
    // siftup: check from child to father, if child > father, siftup child
    // o(nlogn), every entry has duplicated accesses
    // Based on top father to bottom child, once top father is checked,
    //  the bottom child may siftup to the top father again
    //  The depth of siftup is logn, worst case number of siftup is n
    //  => worst o(nlogn)
    void siftup(vector<int>& nums, int k) {
        int len = nums.size();
        while (k > 0) {
            // find child > father
            int father = (k - 1) / 2;
            if (nums[k] > nums[father]) {
                break;
            }
            // swap, put min to the front
            swap(nums[k], nums[father]);
            k = father;
        }
        return;
    }
};

Similar problems

x

Tags

x