Hykilpikonna
273 lines
24 KiB
HTML
273 lines
24 KiB
HTML
<!DOCTYPE html>
|
||
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
|
||
<head>
|
||
<meta charset="utf-8" />
|
||
<meta name="generator" content="pandoc" />
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
|
||
<title>9.7 Priority Queues</title>
|
||
<style>
|
||
code{white-space: pre-wrap;}
|
||
span.smallcaps{font-variant: small-caps;}
|
||
span.underline{text-decoration: underline;}
|
||
div.column{display: inline-block; vertical-align: top; width: 50%;}
|
||
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
|
||
ul.task-list{list-style: none;}
|
||
pre > code.sourceCode { white-space: pre; position: relative; }
|
||
pre > code.sourceCode > span { display: inline-block; line-height: 1.25; }
|
||
pre > code.sourceCode > span:empty { height: 1.2em; }
|
||
code.sourceCode > span { color: inherit; text-decoration: inherit; }
|
||
div.sourceCode { margin: 1em 0; }
|
||
pre.sourceCode { margin: 0; }
|
||
@media screen {
|
||
div.sourceCode { overflow: auto; }
|
||
}
|
||
@media print {
|
||
pre > code.sourceCode { white-space: pre-wrap; }
|
||
pre > code.sourceCode > span { text-indent: -5em; padding-left: 5em; }
|
||
}
|
||
pre.numberSource code
|
||
{ counter-reset: source-line 0; }
|
||
pre.numberSource code > span
|
||
{ position: relative; left: -4em; counter-increment: source-line; }
|
||
pre.numberSource code > span > a:first-child::before
|
||
{ content: counter(source-line);
|
||
position: relative; left: -1em; text-align: right; vertical-align: baseline;
|
||
border: none; display: inline-block;
|
||
-webkit-touch-callout: none; -webkit-user-select: none;
|
||
-khtml-user-select: none; -moz-user-select: none;
|
||
-ms-user-select: none; user-select: none;
|
||
padding: 0 4px; width: 4em;
|
||
color: #aaaaaa;
|
||
}
|
||
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa; padding-left: 4px; }
|
||
div.sourceCode
|
||
{ }
|
||
@media screen {
|
||
pre > code.sourceCode > span > a:first-child::before { text-decoration: underline; }
|
||
}
|
||
code span.al { color: #ff0000; font-weight: bold; } /* Alert */
|
||
code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
|
||
code span.at { color: #7d9029; } /* Attribute */
|
||
code span.bn { color: #40a070; } /* BaseN */
|
||
code span.bu { } /* BuiltIn */
|
||
code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
|
||
code span.ch { color: #4070a0; } /* Char */
|
||
code span.cn { color: #880000; } /* Constant */
|
||
code span.co { color: #60a0b0; font-style: italic; } /* Comment */
|
||
code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
|
||
code span.do { color: #ba2121; font-style: italic; } /* Documentation */
|
||
code span.dt { color: #902000; } /* DataType */
|
||
code span.dv { color: #40a070; } /* DecVal */
|
||
code span.er { color: #ff0000; font-weight: bold; } /* Error */
|
||
code span.ex { } /* Extension */
|
||
code span.fl { color: #40a070; } /* Float */
|
||
code span.fu { color: #06287e; } /* Function */
|
||
code span.im { } /* Import */
|
||
code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
|
||
code span.kw { color: #007020; font-weight: bold; } /* Keyword */
|
||
code span.op { color: #666666; } /* Operator */
|
||
code span.ot { color: #007020; } /* Other */
|
||
code span.pp { color: #bc7a00; } /* Preprocessor */
|
||
code span.sc { color: #4070a0; } /* SpecialChar */
|
||
code span.ss { color: #bb6688; } /* SpecialString */
|
||
code span.st { color: #4070a0; } /* String */
|
||
code span.va { color: #19177c; } /* Variable */
|
||
code span.vs { color: #4070a0; } /* VerbatimString */
|
||
code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
|
||
</style>
|
||
<link rel="stylesheet" href="../tufte.css" />
|
||
<script src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js" type="text/javascript"></script>
|
||
<!--[if lt IE 9]>
|
||
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
|
||
<![endif]-->
|
||
</head>
|
||
<body>
|
||
<div style="display:none">
|
||
\(
|
||
\newcommand{\NOT}{\neg}
|
||
\newcommand{\AND}{\wedge}
|
||
\newcommand{\OR}{\vee}
|
||
\newcommand{\XOR}{\oplus}
|
||
\newcommand{\IMP}{\Rightarrow}
|
||
\newcommand{\IFF}{\Leftrightarrow}
|
||
\newcommand{\TRUE}{\text{True}\xspace}
|
||
\newcommand{\FALSE}{\text{False}\xspace}
|
||
\newcommand{\IN}{\,{\in}\,}
|
||
\newcommand{\NOTIN}{\,{\notin}\,}
|
||
\newcommand{\TO}{\rightarrow}
|
||
\newcommand{\DIV}{\mid}
|
||
\newcommand{\NDIV}{\nmid}
|
||
\newcommand{\MOD}[1]{\pmod{#1}}
|
||
\newcommand{\MODS}[1]{\ (\text{mod}\ #1)}
|
||
\newcommand{\N}{\mathbb N}
|
||
\newcommand{\Z}{\mathbb Z}
|
||
\newcommand{\Q}{\mathbb Q}
|
||
\newcommand{\R}{\mathbb R}
|
||
\newcommand{\C}{\mathbb C}
|
||
\newcommand{\cA}{\mathcal A}
|
||
\newcommand{\cB}{\mathcal B}
|
||
\newcommand{\cC}{\mathcal C}
|
||
\newcommand{\cD}{\mathcal D}
|
||
\newcommand{\cE}{\mathcal E}
|
||
\newcommand{\cF}{\mathcal F}
|
||
\newcommand{\cG}{\mathcal G}
|
||
\newcommand{\cH}{\mathcal H}
|
||
\newcommand{\cI}{\mathcal I}
|
||
\newcommand{\cJ}{\mathcal J}
|
||
\newcommand{\cL}{\mathcal L}
|
||
\newcommand{\cK}{\mathcal K}
|
||
\newcommand{\cN}{\mathcal N}
|
||
\newcommand{\cO}{\mathcal O}
|
||
\newcommand{\cP}{\mathcal P}
|
||
\newcommand{\cQ}{\mathcal Q}
|
||
\newcommand{\cS}{\mathcal S}
|
||
\newcommand{\cT}{\mathcal T}
|
||
\newcommand{\cV}{\mathcal V}
|
||
\newcommand{\cW}{\mathcal W}
|
||
\newcommand{\cZ}{\mathcal Z}
|
||
\newcommand{\emp}{\emptyset}
|
||
\newcommand{\bs}{\backslash}
|
||
\newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor}
|
||
\newcommand{\ceil}[1]{\left \lceil #1 \right \rceil}
|
||
\newcommand{\abs}[1]{\left | #1 \right |}
|
||
\newcommand{\xspace}{}
|
||
\newcommand{\proofheader}[1]{\underline{\textbf{#1}}}
|
||
\)
|
||
</div>
|
||
<header id="title-block-header">
|
||
<h1 class="title">9.7 Priority Queues</h1>
|
||
</header>
|
||
<section>
|
||
<p>Not all lineups work the same way. While the lineup at a McDonald’s restaurant serves customers in a first-in-first-out order, the emergency room at a hospital does not see patients in the order that they arrive. Instead, the medical team perform an initial assessment of each patient for the severity of their illness, and patients with more life-threatening issues are seen earlier than others, regardless of when they arrived. In other words, patients are <em>prioritized</em> based on their condition.</p>
|
||
<h2 id="the-priority-queue-adt">The Priority Queue ADT</h2>
|
||
<p>The <strong>Priority Queue ADT</strong> is similar to the Queue ADT, except that every item has some measure of its “priority”. Items are removed from a Priority Queue in order of their priority, and ties are broken in FIFO order. To summarize:</p>
|
||
<ul>
|
||
<li><strong>Priority Queue</strong>
|
||
<ul>
|
||
<li>Data: a collection of items and their priorities</li>
|
||
<li>Operations: determine whether the priority queue is empty, add an item with a priority (<em>enqueue</em>), remove the highest priority item (<em>dequeue</em>)</li>
|
||
</ul></li>
|
||
</ul>
|
||
<p>One subtlety with our definition of this ADT is in how we represent priorities. For this section, we’ll simply represent priorities as integers, with larger integers representing higher priorities. We’ll see a different way of representing priorites in the next chapter.</p>
|
||
<p>Here is the public interface of a <code>PriorityQueue</code> class.</p>
|
||
<div class="sourceCode" id="cb1"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb1-1"><a href="#cb1-1"></a><span class="kw">class</span> PriorityQueue:</span>
|
||
<span id="cb1-2"><a href="#cb1-2"></a> <span class="co">"""A collection items that are be removed in priority order.</span></span>
|
||
<span id="cb1-3"><a href="#cb1-3"></a></span>
|
||
<span id="cb1-4"><a href="#cb1-4"></a><span class="co"> When removing an item from the queue, the highest-priority item is the one</span></span>
|
||
<span id="cb1-5"><a href="#cb1-5"></a><span class="co"> that is removed.</span></span>
|
||
<span id="cb1-6"><a href="#cb1-6"></a></span>
|
||
<span id="cb1-7"><a href="#cb1-7"></a><span class="co"> >>> pq = PriorityQueue()</span></span>
|
||
<span id="cb1-8"><a href="#cb1-8"></a><span class="co"> >>> pq.is_empty()</span></span>
|
||
<span id="cb1-9"><a href="#cb1-9"></a><span class="co"> True</span></span>
|
||
<span id="cb1-10"><a href="#cb1-10"></a><span class="co"> >>> pq.enqueue(1, 'hello')</span></span>
|
||
<span id="cb1-11"><a href="#cb1-11"></a><span class="co"> >>> pq.is_empty()</span></span>
|
||
<span id="cb1-12"><a href="#cb1-12"></a><span class="co"> False</span></span>
|
||
<span id="cb1-13"><a href="#cb1-13"></a><span class="co"> >>> pq.enqueue(5, 'goodbye')</span></span>
|
||
<span id="cb1-14"><a href="#cb1-14"></a><span class="co"> >>> pq.enqueue(2, 'hi')</span></span>
|
||
<span id="cb1-15"><a href="#cb1-15"></a><span class="co"> >>> pq.dequeue()</span></span>
|
||
<span id="cb1-16"><a href="#cb1-16"></a><span class="co"> 'goodbye'</span></span>
|
||
<span id="cb1-17"><a href="#cb1-17"></a><span class="co"> """</span></span>
|
||
<span id="cb1-18"><a href="#cb1-18"></a></span>
|
||
<span id="cb1-19"><a href="#cb1-19"></a> <span class="kw">def</span> <span class="fu">__init__</span>(<span class="va">self</span>) <span class="op">-></span> <span class="va">None</span>:</span>
|
||
<span id="cb1-20"><a href="#cb1-20"></a> <span class="co">"""Initialize a new and empty priority queue."""</span></span>
|
||
<span id="cb1-21"><a href="#cb1-21"></a></span>
|
||
<span id="cb1-22"><a href="#cb1-22"></a> <span class="kw">def</span> is_empty(<span class="va">self</span>) <span class="op">-></span> <span class="bu">bool</span>:</span>
|
||
<span id="cb1-23"><a href="#cb1-23"></a> <span class="co">"""Return whether this priority queue contains no items.</span></span>
|
||
<span id="cb1-24"><a href="#cb1-24"></a><span class="co"> """</span></span>
|
||
<span id="cb1-25"><a href="#cb1-25"></a></span>
|
||
<span id="cb1-26"><a href="#cb1-26"></a> <span class="kw">def</span> enqueue(<span class="va">self</span>, priority: <span class="bu">int</span>, item: Any) <span class="op">-></span> <span class="va">None</span>:</span>
|
||
<span id="cb1-27"><a href="#cb1-27"></a> <span class="co">"""Add the given item with the given priority to this priority queue.</span></span>
|
||
<span id="cb1-28"><a href="#cb1-28"></a><span class="co"> """</span></span>
|
||
<span id="cb1-29"><a href="#cb1-29"></a></span>
|
||
<span id="cb1-30"><a href="#cb1-30"></a> <span class="kw">def</span> dequeue(<span class="va">self</span>) <span class="op">-></span> Any:</span>
|
||
<span id="cb1-31"><a href="#cb1-31"></a> <span class="co">"""Remove and return the item with the highest priority.</span></span>
|
||
<span id="cb1-32"><a href="#cb1-32"></a></span>
|
||
<span id="cb1-33"><a href="#cb1-33"></a><span class="co"> Raise an EmptyPriorityQueueError when the priority queue is empty.</span></span>
|
||
<span id="cb1-34"><a href="#cb1-34"></a><span class="co"> """</span></span>
|
||
<span id="cb1-35"><a href="#cb1-35"></a></span>
|
||
<span id="cb1-36"><a href="#cb1-36"></a></span>
|
||
<span id="cb1-37"><a href="#cb1-37"></a><span class="kw">class</span> EmptyPriorityQueueError(<span class="pp">Exception</span>):</span>
|
||
<span id="cb1-38"><a href="#cb1-38"></a> <span class="co">"""Exception raised when calling pop on an empty stack."""</span></span>
|
||
<span id="cb1-39"><a href="#cb1-39"></a></span>
|
||
<span id="cb1-40"><a href="#cb1-40"></a> <span class="kw">def</span> <span class="fu">__str__</span>(<span class="va">self</span>) <span class="op">-></span> <span class="bu">str</span>:</span>
|
||
<span id="cb1-41"><a href="#cb1-41"></a> <span class="co">"""Return a string representation of this error."""</span></span>
|
||
<span id="cb1-42"><a href="#cb1-42"></a> <span class="cf">return</span> <span class="st">'You called dequeue on an empty priority queue.'</span></span></code></pre></div>
|
||
<h2 id="list-based-implementation-of-the-priority-queue-adt">List-based implementation of the Priority Queue ADT</h2>
|
||
<p>Unlike with the Stack and Queue ADTs, it is not clear if we can use a list here. Somehow we need to not only store items, but also keep track of which one has the largest priority, and in the case of ties, which one was inserted first.</p>
|
||
<p>Our implementation idea here is to use a private attribute that is a <em>list of tuples</em>, where each tuple is a <code>(priority, item)</code> pair. Our list will also be <em>sorted</em> with respect to priority (breaking ties by insertion order), so that the <em>last</em> element in the list is always the next item to be removed from the priority queue.</p>
|
||
<p>With this idea, three of the four <code>PriorityQueue</code> methods are straightforward to implement:</p>
|
||
<div class="sourceCode" id="cb2"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb2-1"><a href="#cb2-1"></a><span class="im">from</span> typing <span class="im">import</span> Any</span>
|
||
<span id="cb2-2"><a href="#cb2-2"></a></span>
|
||
<span id="cb2-3"><a href="#cb2-3"></a></span>
|
||
<span id="cb2-4"><a href="#cb2-4"></a><span class="kw">class</span> PriorityQueue:</span>
|
||
<span id="cb2-5"><a href="#cb2-5"></a> <span class="co">"""A queue of items that can be dequeued in priority order.</span></span>
|
||
<span id="cb2-6"><a href="#cb2-6"></a></span>
|
||
<span id="cb2-7"><a href="#cb2-7"></a><span class="co"> When removing an item from the queue, the highest-priority item is the one</span></span>
|
||
<span id="cb2-8"><a href="#cb2-8"></a><span class="co"> that is removed.</span></span>
|
||
<span id="cb2-9"><a href="#cb2-9"></a><span class="co"> """</span></span>
|
||
<span id="cb2-10"><a href="#cb2-10"></a> <span class="co"># Private Instance Attributes:</span></span>
|
||
<span id="cb2-11"><a href="#cb2-11"></a> <span class="co"># - _items: a list of the items in this priority queue</span></span>
|
||
<span id="cb2-12"><a href="#cb2-12"></a> _items: <span class="bu">list</span>[<span class="bu">tuple</span>[<span class="bu">int</span>, Any]]</span>
|
||
<span id="cb2-13"><a href="#cb2-13"></a></span>
|
||
<span id="cb2-14"><a href="#cb2-14"></a> <span class="kw">def</span> <span class="fu">__init__</span>(<span class="va">self</span>) <span class="op">-></span> <span class="va">None</span>:</span>
|
||
<span id="cb2-15"><a href="#cb2-15"></a> <span class="co">"""Initialize a new and empty priority queue."""</span></span>
|
||
<span id="cb2-16"><a href="#cb2-16"></a> <span class="va">self</span>._items <span class="op">=</span> []</span>
|
||
<span id="cb2-17"><a href="#cb2-17"></a></span>
|
||
<span id="cb2-18"><a href="#cb2-18"></a> <span class="kw">def</span> is_empty(<span class="va">self</span>) <span class="op">-></span> <span class="bu">bool</span>:</span>
|
||
<span id="cb2-19"><a href="#cb2-19"></a> <span class="co">"""Return whether this priority queue contains no items.</span></span>
|
||
<span id="cb2-20"><a href="#cb2-20"></a><span class="co"> """</span></span>
|
||
<span id="cb2-21"><a href="#cb2-21"></a> <span class="cf">return</span> <span class="va">self</span>._items <span class="op">==</span> []</span>
|
||
<span id="cb2-22"><a href="#cb2-22"></a></span>
|
||
<span id="cb2-23"><a href="#cb2-23"></a> <span class="kw">def</span> dequeue(<span class="va">self</span>) <span class="op">-></span> Any:</span>
|
||
<span id="cb2-24"><a href="#cb2-24"></a> <span class="co">"""Remove and return the item with the highest priority.</span></span>
|
||
<span id="cb2-25"><a href="#cb2-25"></a></span>
|
||
<span id="cb2-26"><a href="#cb2-26"></a><span class="co"> Raise an EmptyPriorityQueueError when the priority queue is empty.</span></span>
|
||
<span id="cb2-27"><a href="#cb2-27"></a><span class="co"> """</span></span>
|
||
<span id="cb2-28"><a href="#cb2-28"></a> <span class="cf">if</span> <span class="va">self</span>.is_empty():</span>
|
||
<span id="cb2-29"><a href="#cb2-29"></a> <span class="cf">raise</span> EmptyPriorityQueueError</span>
|
||
<span id="cb2-30"><a href="#cb2-30"></a> <span class="cf">else</span>:</span>
|
||
<span id="cb2-31"><a href="#cb2-31"></a> _priority, item <span class="op">=</span> <span class="va">self</span>._items.pop()</span>
|
||
<span id="cb2-32"><a href="#cb2-32"></a> <span class="cf">return</span> item</span></code></pre></div>
|
||
<p>As an exercise, we’ll leave you to show that each of these operations also runs in <span class="math inline">\(\Theta(1)\)</span> time. But what about <code>PriorityQueue.enqueue</code>? An initial approach might be to first insert the new priority and item into the list, and then sort the list by priority. But this is a bit inefficient: we shouldn’t need to re-sort the entire list, if we start with a sorted list and are simply inserting one new item.<label for="sn-0" class="margin-toggle sidenote-number"></label><input type="checkbox" id="sn-0" class="margin-toggle"/><span class="sidenote"> We make this observation precise by observing that the worst-case running time of <code>list.sort</code> is <span class="math inline">\(\Theta(n \log n)\)</span>. We’ll study sorting algorithms in detail later on this year.</span> So instead, our <code>enqueue</code> implementation will search for the right index in the list to add the new item. For example, suppose we want to insert the item <code>'hi'</code> with priority <code>5</code> into the priority queue with <code>self._items</code> equal to <code>[(1, 'a'), (4, 'b'), (6, 'c'), (10, 'd')]</code>. We need to insert <code>(5, 'hi')</code> into index 2 in this list:</p>
|
||
<p><img src="./images/priority_queue_enqueue.png" alt="A diagram of priority queue enqueue" /><br />
|
||
</p>
|
||
<p>Here is our implementation of <code>enqueue</code>:</p>
|
||
<div class="sourceCode" id="cb3"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb3-1"><a href="#cb3-1"></a><span class="kw">class</span> PriorityQueue:</span>
|
||
<span id="cb3-2"><a href="#cb3-2"></a> ...</span>
|
||
<span id="cb3-3"><a href="#cb3-3"></a></span>
|
||
<span id="cb3-4"><a href="#cb3-4"></a> <span class="kw">def</span> enqueue(<span class="va">self</span>, priority: <span class="bu">int</span>, item: Any) <span class="op">-></span> <span class="va">None</span>:</span>
|
||
<span id="cb3-5"><a href="#cb3-5"></a> <span class="co">"""Add the given item with the given priority to this priority queue.</span></span>
|
||
<span id="cb3-6"><a href="#cb3-6"></a><span class="co"> """</span></span>
|
||
<span id="cb3-7"><a href="#cb3-7"></a> i <span class="op">=</span> <span class="dv">0</span></span>
|
||
<span id="cb3-8"><a href="#cb3-8"></a> <span class="cf">while</span> i <span class="op"><</span> <span class="bu">len</span>(<span class="va">self</span>._items) <span class="kw">and</span> <span class="va">self</span>._items[i][<span class="dv">0</span>] <span class="op"><</span> priority:</span>
|
||
<span id="cb3-9"><a href="#cb3-9"></a> <span class="co"># Loop invariant: all items in self._items[0:i]</span></span>
|
||
<span id="cb3-10"><a href="#cb3-10"></a> <span class="co"># have a lower priority than <priority>.</span></span>
|
||
<span id="cb3-11"><a href="#cb3-11"></a> i <span class="op">=</span> i <span class="op">+</span> <span class="dv">1</span></span>
|
||
<span id="cb3-12"><a href="#cb3-12"></a></span>
|
||
<span id="cb3-13"><a href="#cb3-13"></a> <span class="va">self</span>._items.insert(i, (priority, item))</span></code></pre></div>
|
||
<p>In the second part of the loop condition, you might wonder about the <code><</code>: could we do <code>self._items[i][0] <= priority</code> instead? Does it make a difference? It turns out that switching <code><</code> for <code><=</code> in the second part of the condition does make a difference when it comes to breaking ties. We’ll leave it as an exercise for you to work this out: try tracing an <code>enqueue</code> operation for the item <code>'hi'</code> with priority <code>5</code> into the priority queue with <code>self._items</code> equal to <code>[(1, 'a'), (5, 'b'), (5, 'c'), (10, 'd')]</code>.</p>
|
||
<p>And finally, what is the running time of this implementation of <code>PriorityQueue.enqueue</code>, for a priority queue with <span class="math inline">\(n\)</span> elements? The loop here is a bit tricky to analyze because the number of iterations is not a fixed number in terms of <span class="math inline">\(n\)</span>. Here is one analysis:</p>
|
||
<ul>
|
||
<li><p>The while loop takes <em>at most</em> <span class="math inline">\(n\)</span> iterations, since <code>i</code> starts at 0 and increases by 1 at each iteration, and the loop must stop when <code>i</code> reaches <span class="math inline">\(n\)</span> (if it hasn’t stopped earlier).</p>
|
||
<p>Since each loop iteration takes 1 step, in total the while loop takes at most <span class="math inline">\(n\)</span> steps.</p></li>
|
||
<li><p>We know from our study of array-based lists that <code>list.insert</code> takes at most <span class="math inline">\(n\)</span> steps, where <span class="math inline">\(n\)</span> is the length of the list being inserted into.</p></li>
|
||
<li><p>Adding up these two quantities, the total running time of this algorithm is at most <span class="math inline">\(n + n = 2n\)</span> steps, which is <span class="math inline">\(\cO(n)\)</span>.</p></li>
|
||
</ul>
|
||
<p>Of course, we shouldn’t be satisfied with just an upper bound on the running time! It turns out that we can do better by incorporating the value of variable <code>i</code> in our calculation. Let <span class="math inline">\(I\)</span> be the value of variable <code>i</code> <em>after</em> the loop finishes. Then:</p>
|
||
<ul>
|
||
<li>We now know that the while loop takes <em>exactly</em> <span class="math inline">\(I\)</span> iterations, for a total of <span class="math inline">\(I\)</span> steps (1 step per iteration).</li>
|
||
<li>We know that calling <code>list.insert</code> on a list of length <span class="math inline">\(n\)</span> to insert an item at index <span class="math inline">\(I\)</span> takes <span class="math inline">\(n - I\)</span> steps.</li>
|
||
<li>So the total running time is actually <span class="math inline">\(I + (n - I) = n\)</span> steps, which is <span class="math inline">\(\Theta(n)\)</span>.</li>
|
||
</ul>
|
||
<p>In other words, we’ve shown that <em>every</em> call to this implementation of <code>PriorityQueue.enqueue</code> will take <span class="math inline">\(\Theta(n)\)</span> time, regardless of the priority being inserted.</p>
|
||
<h3 id="using-an-unsorted-list">Using an unsorted list</h3>
|
||
<p>Our implementation of <code>PriorityQueue</code> has a constant-time <code>dequeue</code> but a linear-time <code>enqueue</code>. You might naturally wonder if we can do better: what if we used an unsorted list of tuples instead? This would allow us to have <span class="math inline">\(\Theta(1)\)</span> <code>enqueue</code> operations, simply by appending a new <code>(priority, item)</code> tuple to the end of <code>self._items</code>. However, we have simply shifted the work over to the <code>dequeue</code> operation. Specifically, we must search for the highest priority item in a list of unsorted items, which would take <span class="math inline">\(\Theta(n)\)</span> time. Yet another trade-off!</p>
|
||
<h3 id="looking-ahead-heaps">Looking ahead: heaps</h3>
|
||
<p>In CSC263/CSC265, you’ll learn about the <em>heap</em>, a data structure which is commonly used to implement the Priority Queue ADT in practice. We can use this data structure to implement both <code>PriorityQueue.enqueue</code> and <code>PriorityQueue.dequeue</code> with a worst-case running time of <span class="math inline">\(\Theta(\log n)\)</span>.<label for="sn-1" class="margin-toggle sidenote-number"></label><input type="checkbox" id="sn-1" class="margin-toggle"/><span class="sidenote"> This is actually the approach taken by Python’s built-in <a href="https://docs.python.org/3/library/heapq.html"><code>heapq</code> module</a>. Pretty neat!</span></p>
|
||
</section>
|
||
<footer>
|
||
<a href="https://www.teach.cs.toronto.edu/~csc110y/fall/notes/">CSC110 Course Notes Home</a>
|
||
</footer>
|
||
</body>
|
||
</html>
|