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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
<?php
/**
* Zend Framework
*
* LICENSE
*
* This source file is subject to the new BSD license that is bundled
* with this package in the file LICENSE.txt.
* It is also available through the world-wide-web at this URL:
* http://framework.zend.com/license/new-bsd
* If you did not receive a copy of the license and are unable to
* obtain it through the world-wide-web, please send an email
* to license@zend.com so we can send you a copy immediately.
*
* @category Zend
* @package Zend_Search_Lucene
* @copyright Copyright (c) 2005-2010 Zend Technologies USA Inc. (http://www.zend.com)
* @license http://framework.zend.com/license/new-bsd New BSD License
* @version $Id: PriorityQueue.php 20096 2010-01-06 02:05:09Z bkarwin $
*/
/**
* Abstract Priority Queue
*
* It implements a priority queue.
* Please go to "Data Structures and Algorithms",
* Aho, Hopcroft, and Ullman, Addison-Wesley, 1983 (corrected 1987 edition),
* for implementation details.
*
* It provides O(log(N)) time of put/pop operations, where N is a size of queue
*
* @category Zend
* @package Zend_Search_Lucene
* @copyright Copyright (c) 2005-2010 Zend Technologies USA Inc. (http://www.zend.com)
* @license http://framework.zend.com/license/new-bsd New BSD License
*/
abstract class Zend_Search_Lucene_PriorityQueue
{
/**
* Queue heap
*
* Heap contains balanced partial ordered binary tree represented in array
* [0] - top of the tree
* [1] - first child of [0]
* [2] - second child of [0]
* ...
* [2*n + 1] - first child of [n]
* [2*n + 2] - second child of [n]
*
* @var array
*/
private $_heap = array();
/**
* Add element to the queue
*
* O(log(N)) time
*
* @param mixed $element
*/
public function put($element)
{
$nodeId = count($this->_heap);
$parentId = ($nodeId-1) >> 1; // floor( ($nodeId-1)/2 )
while ($nodeId != 0 && $this->_less($element, $this->_heap[$parentId])) {
// Move parent node down
$this->_heap[$nodeId] = $this->_heap[$parentId];
// Move pointer to the next level of tree
$nodeId = $parentId;
$parentId = ($nodeId-1) >> 1; // floor( ($nodeId-1)/2 )
}
// Put new node into the tree
$this->_heap[$nodeId] = $element;
}
/**
* Return least element of the queue
*
* Constant time
*
* @return mixed
*/
public function top()
{
if (count($this->_heap) == 0) {
return null;
}
return $this->_heap[0];
}
/**
* Removes and return least element of the queue
*
* O(log(N)) time
*
* @return mixed
*/
public function pop()
{
if (count($this->_heap) == 0) {
return null;
}
$top = $this->_heap[0];
$lastId = count($this->_heap) - 1;
/**
* Find appropriate position for last node
*/
$nodeId = 0; // Start from a top
$childId = 1; // First child
// Choose smaller child
if ($lastId > 2 && $this->_less($this->_heap[2], $this->_heap[1])) {
$childId = 2;
}
while ($childId < $lastId &&
$this->_less($this->_heap[$childId], $this->_heap[$lastId])
) {
// Move child node up
$this->_heap[$nodeId] = $this->_heap[$childId];
$nodeId = $childId; // Go down
$childId = ($nodeId << 1) + 1; // First child
// Choose smaller child
if (($childId+1) < $lastId &&
$this->_less($this->_heap[$childId+1], $this->_heap[$childId])
) {
$childId++;
}
}
// Move last element to the new position
$this->_heap[$nodeId] = $this->_heap[$lastId];
unset($this->_heap[$lastId]);
return $top;
}
/**
* Clear queue
*/
public function clear()
{
$this->_heap = array();
}
/**
* Compare elements
*
* Returns true, if $el1 is less than $el2; else otherwise
*
* @param mixed $el1
* @param mixed $el2
* @return boolean
*/
abstract protected function _less($el1, $el2);
}
|
