-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge_k_sorted_lists.php
92 lines (74 loc) · 2.11 KB
/
merge_k_sorted_lists.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
<?php
/**
* Merge K Sorted Lists
* @link https://leetcode.com/problems/merge-k-sorted-lists
*
* Approach:
* Take all nodes of all Lists and push them to the Array
* Heapify Array so, it will be MinHeap
* Extract min value from the MinHeap until Heap is not empty
*
* m = number of linked lists
* n = number of nodes in i-th linked list
* Time Complexity - O(m * n log n)
* Space Complexity - O(m * n)
*/
class Solution {
private array $heap = [];
public function mergeKLists($lists)
{
if (empty($lists)) {
return [];
}
for ($i = 0; $i < count($lists); $i++) {
$node = $lists[$i];
while ($node) {
$this->heap[] = $node;
$node = $node->next;
}
}
$this->heapify();
$head = $this->extractMin();
$node = $head;
while ($node) {
$node->next = $this->extractMin();
$node = $node->next;
}
return $head;
}
protected function heapify()
{
for ($i = floor(count($this->heap) / 2 - 1); $i >= 0; $i--) {
$this->bubbleDown($i);
}
}
protected function bubbleDown($current)
{
$leftChild = $current * 2 + 1;
$rightChild = $current * 2 + 2;
if (($this->heap[$leftChild]->val ?? PHP_INT_MAX) < ($this->heap[$rightChild]->val ?? PHP_INT_MAX)) {
$minChild = $leftChild;
} else {
$minChild = $rightChild;
}
if (($this->heap[$minChild]->val ?? PHP_INT_MAX) < $this->heap[$current]->val) {
$tmp = $this->heap[$current];
$this->heap[$current] = $this->heap[$minChild];
$this->heap[$minChild] = $tmp;
$this->bubbleDown($minChild);
}
}
protected function extractMin()
{
if (empty($this->heap)) {
return null;
}
if (count($this->heap) === 1) {
return array_pop($this->heap);
}
$min = $this->heap[0];
$this->heap[0] = array_pop($this->heap);
$this->bubbleDown(0);
return $min;
}
}