堆以及堆排序

1. 堆

　　堆是一颗被完全填满的二叉树，可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。对于一个n个节点的完全二叉树，树高为logN.

一个重要的观察发现，因为完全二叉树很有规律，所以可以用一个数组表示而不需要使用链。这种用数组表示树的方法称为隐式表述法(implicit representation)

　　二叉堆有两种形式:最大堆和最小堆。在最大堆中，父节点的值总是大于等于任何一个子节点的值。因此，堆中的最大元素放在根节点中，并且在任一子树中，该字数包含的所有节点的值都不大于该子树根节点的值。最小堆是指父节点的值总是小于或等于任一子节点的值。

      

　　在堆排序算法中，我们使用最大堆。最小堆通常用于构造优先队列。

2.堆的存储

　　一般都用数组来表示堆。一般位置0不用来存储元素，即存储区域为A[1,...,len]。所以对于一个节点。它的父节点的下标为2/i，左孩子的下标为2*i，右孩子的节点为2*i+1.

　　如果要使用下标为0的位置，那么父节点的下标就为(i-1)/2。它的左右子节点下标为2*i+1和2*i+2。

　　本文中将不使用0位置。

3. 向下调整

　　向下调整是为了维护堆的性质。它的输入为数组A和下标i。它首先看该节点是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换。交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到该节点为根的子结构成堆为止。时间复杂度为O(lgn)

　　

void AdjustDown(ElemType A[], int k, int heap_size) {
    int child;
    ElemType tmp = A[i];

    for (int i = k << 1; i <= heap_size; i *= 2) { // 沿键值较大的子节点向下筛选
        if (i < heap_size && A[i + 1] > A[i]) {
            i++;
        }
        if (A[child] < tmp) {
            A[k] = A[child]; //将A[child]调整到双亲的位置
            k = i;             //修改键值,以便继续向下筛选
        } else {
            break;
        }

    }

    a[k] = tmp;                //被筛选的值放入最终的位置
 }

　　算法导论中给出的递归的方法：

inline int Left(int i) {
    return i << 1;
}

inline int Right(int i) {
    return i << 1 + 1;
}

void AdjustDown(int A[], int k, int heap_size) {
    int left_child = Left(k);
    int right_child = Right(k);

    int largest = k;

    if (left_child <= heap_size && A[left_child] > A[largest]) {
        largest = leftc_child;
    }
    if (right_child <= heap_size && A[right_child] > A[largest]) {
        largest = right_child;
    }

    if (largest != k) {
        swap(A[k], A[largest]);
        AdjustDown(A, largest, heap_size);
    }

4.建堆

　

void BuildMaxHeap(ElemType A[], int len) {
    for (int i = len / 2; i > 0; --i) //下标从0开始，i = len / 2 - 1; i>= 0; --i
        AdjustDown(A, i, len);　　     //AdjustDown(A,ilen - 1):
}

5.向上操作与堆的插入操作

　　堆的插入操作时，先将新节点放在堆的末端，在对这个新节点执行向上调整操作。假设新插入的节点在下标为k的位置。此项操作意味着二叉堆的数据从数组下标1处开始。

　　

//下标从1开始
template<typename T> 
void PercolateUp(vector<T> &data, int i) {
    T temp = data[i];
    for (; i > 1 && temp > data[i / 2]; i /= 2) {
        data[i] = data[i / 2];
    }

    data[i] = temp;
}

//下标从0开始
template<typename T> 
void PercolateUp(vector<T> &data, int i) {
    T temp = data[i];
    for (; i > 0 && temp > data[(i-1)/2]; i = (i - 1) / 2) {
        data[i] = data[(i-1)/2];
    }

    data[i] = temp;
}

6.堆排序

　　堆排序首先将存放在L[1..n]中的n个元素建立成初始堆，由于堆本身的特点，堆顶元素就是最大值。输出堆顶的元素，通常将堆底的元素送入堆顶。此时根节点已不满足堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持最大堆的性质，输出堆顶元素。如此重复直到堆中元素剩下一个元素为止。

　　对于存储从下标1开始：

　　

void HeapSort(int A[], int len) {
    BuildMaxHeap(A,len);
    for (int i = len; i > 1; --i) {
        swap(A[i], A[1]);
        AdjustDown(A, 1, i - 1);
    }
}

　　　对于存储下标从0开始：

　　

int Left(int i) {
    return (i << 1) + 1;
}

void AdjustDown(int A[], int i, int n) {
    int temp = a[i];

    for (int child = Left(i); child <= n; i = child ) {
        if (child < n && A[child] < A[child + 1]) 
            ++child;
        if (temp < A[child])
            A[i] = A[child];
        else
            break;
    }

    A[i] = temp;

}

void HeapSort(int A[], int len) {
    for (int i = len / 2 - 1; i >= 0; --i) {
        AdjustDown(A, i, len);
    }
    for (int i = len - 1; i > 0; --i) {
        swap(A[0], A[i]);
        AdjustDown(A, 0, i - 1);
    }
}

堆的相关题目：

　　1. 最小的k个数

　　　输入n个整数，输出其中最小的k个数。例如输入1,2,3,4,5,6,7,8这8个数字，则最小的4个数字是1,2，3和4.（《王道程序员求职宝典》）

　　　解答：可以使用快排的partition来解决此题，时间复杂度为O(N).但此种方法也有限制。首先需要一次性读入所有数据，其次，需要修改输入的数组。

　　　首先我们读入k个数创建一个大小为k的大根堆，然以后我们依次读入剩余数据，如果当前数据比大根堆的堆顶小，则用这个数替换当前堆顶，并调整使其保持　

　　　大根堆的性质；如果当前数据比堆顶大，那么这个数不可能是最小的k个整数之一，故可以抛弃。

　　　其中，BuildMaxHeap函数与AdjustDown函数为前面提到的函数。

　　　当需要求最大的k个数时，只需要将大根堆改为小根堆即可。

　　　时间复杂度为O(NlogK)

　　　

void PercolateDown(vector<int> &data, int i, int heap_size) {
    int temp = data[i];

    for (int child = i * 2 + 1; child <= heap_size;child = child * 2 + 1) {
        if (child < heap_size && data[child + 1] > data[child]) 
            child++;

        if (temp < data[child]) {
            data[i] = data[child];
            i = child;
        } else {
            break;
        }
    }

    data[i] = temp;
}

void BuildMaxHeap(vector<int> &data) {
    for (int i = data.size() / 2 - 1; i >= 0; --i) {
        PercolateDown(data,i,data.size() - 1);
    }
}

vector<int> FindSmallestK(vector<int> &data, int k) {
    vector<int> res(k);
    if (data.empty() || k > data.size())
        return res;

    for (int i = 0; i < k; ++i) 
        res[i] = data[i];

    BuildMaxHeap(res);

    for (int i = k; i < data.size(); ++i) {
        if (data[i] < res[0]) {
            res[0] = data[i];
            PercolateDown(res, 0, k);
        }
    }

    return res;
}

2. 设计一个时间复杂度为O(nlgk) 的算法，它能将k个有序链表合并成一个有序链表，这里了k是所有输入链表包含的总的元素个数（算法导论，P93）

编程思路：

假设k个链表都是非降序排列的。

（1）取k个元素建立最小堆，这k个元素分别是k个链表的第一个元素。建堆的时间复杂度O(k)。

（2）堆顶元素就是k个链表中最小的那个元素，取出它。时间复杂度O(1)。

（3）若堆顶元素所在链表不为空，则取下一个元素放到堆顶位置，这可能破坏了最小堆性质，所以进行堆调整。堆调整时间复杂度O(lgk)。若为空，则此子链表已经被合并完毕，则删除最小堆的堆顶元素，此时最小堆的heapSize减小了1 。删除指定元素时间复杂度O(lgk)。

（4）重复步骤（2）~（3）n-k次。总的时间复杂度是O(k)+O(nlgk)即O(nlgk)。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL){}
};

bool cmp(ListNode *l1, ListNode *l2) {
    return l1->val > l2->val;
}

ListNode *mergeKLists(vector<ListNode *> &lists) {
    vector<ListNode *> heap;

    for (int i = 0; i < lists.size(); ++i) {
        if (lists[i] != NULL)
            heap.push_back(lists[i]);
    }

    make_heap(heap.begin(), heap.end(), cmp);

    ListNode *head = NULL;
    ListNode *curr = NULL;
    while (!heap.empty()) {
        ListNode *min = heap.front();
        pop_heap(heap.begin(), heap.end(), cmp);
        heap.pop_back();

        if (head == NULL)
            head = min;
        if (curr)
            curr->next = min;
        curr = min;

        if (curr->next) {
            heap.push_back(curr->next);
            push_heap(heap.begin(), heap.end(),cmp);
        }
    }

    return head;


}

参考资料：

　　1. 《数据结构与算法分析 C++描述》（第三版）　　人民邮电出版社