# C++ code O(NKlogK) with a easy handmade implementation of heap

• Its time complexity is O(NKlogK), N is the length of a list, K is the number of lists
In this code, it merges K lists at the same time.
for comparison,
if merge one list at a time and merge K-1 times, time is 2N+3N+...+KN = O(NK^2)
if use the way similar to merge sort, time is also O(NKlogK)

``````	void adjust_down(int i, int n, vector<ListNode*>& heap) {
int t;
while ((t = 2 * i + 1) < n) {
if (t + 1 < n && heap[t]->val > heap[t + 1]->val)
++t;
if (heap[t]->val < heap[i]->val) {
ListNode* temp = heap[i];
heap[i] = heap[t];
heap[t] = temp;
i = t;
}
else break;
}
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<ListNode*> heap(lists.size());
int hsize = 0;
for (int i = 0; i < lists.size(); i++)
if (lists[i])
heap[hsize++] = lists[i];

for (int i = hsize / 2 - 1; i >= 0; i--)//construct a heap

while (hsize) {
merged->next = heap[0];
merged = merged->next;
heap[0] = heap[0]->next;
if (!heap[0])
heap[0] = heap[--hsize];