Project P053
Help desk queue
Support tickets with four priorities, served most urgent first and first come, first served within a priority, kept in a binary heap. Open, serve, list the line, change a waiting ticket's priority or cancel it, and see the queue grouped by priority next to what has been served.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-10
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Support tickets wait in one queue and are served most urgent first, and, within each priority, in the order they were opened. Open tickets with one of four priorities - urgent, high, normal, low - serve the next one, see the whole line, change a waiting ticket's priority or cancel it, and see the queue grouped by priority. At most 30 tickets wait at a time.
main.eml- the menu, reading tickets and answers, and the messagesheap.eml- the queue: a binary heap with pushing, serving, removing any ticket, a priority change, and the serving order
How each part works:
- The waiting tickets are a binary min-heap, as in the corpus case
binary-heap: one list, with no links between entries, where the entry at index i has its children at 2i + 1 and 2i + 2. Every parent comes before its children, so the root is always the next ticket to serve. - "Comes before" compares the priority first and then the ticket number. Numbers only grow, so at the same priority the older ticket goes first. Without that second rule a heap would serve equal priorities in no particular order.
- A new ticket goes at the end and moves up while it comes before its parent. Serving takes the root, puts the last entry there, and moves it down below the smaller child until neither child comes before it. Cancelling a ticket from the middle does the same at that index; a priority change moves the ticket up or down from where it is. Each of these touches one path from the root to a leaf, never the whole queue.
- The waiting line is worked out by serving a copy of the heap to the end, so the queue itself is left as it was. The summary puts the waiting tickets in one bucket per priority, as the corpus case
task-priority-bucketersorts tasks into buckets, next to how many of each priority have been served.
What is checked: menu choices 1 to 8; a title of up to 40 characters; a priority from 1 to 4; a ticket number, with or without #, that is waiting; at most 30 waiting tickets. An empty answer cancels.
Sessions: sessions/basic.in opens the eight sample tickets and shows the line: two urgent first, in the order they came, then two high, two normal and two low. - The two urgent tickets are served. - #8 is raised from normal to urgent and goes to the front. - #6 is cancelled. - A new high ticket, #9, goes in behind the two high tickets already waiting, number 4 in line. - The summary has one bucket per priority. Two more tickets are served and the line is shown again.
sessions/bad-input.in gives: - menu choices 0 and x; - every action on the empty queue; - an empty title, a title over 40 characters, and priorities 5, x and an empty one; - tickets x and #99, a change to the priority a ticket already has, and a change and a cancel that are cancelled; - the sample three times, a fourth that would pass 30 tickets, five more tickets up to 30, one too many, and the summary of the full queue.
Built on the verified corpus cases binary-heap (a min-heap with sift up and sift down in one list) and task-priority-bucketer (tasks sorted into priority buckets).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Help desk ==
Tickets are served most urgent first, and in the order they came within a priority.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 0
Pick a number from 1 to 8.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> x
Pick a number from 1 to 8.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 2
No ticket is waiting.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 3
No ticket is waiting.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 4
No ticket is waiting.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 5
No ticket is waiting.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 6
priority waiting served
urgent 0 0
high 0 0
normal 0 0
low 0 0
Waiting 0, served 0, next ticket number #1.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
title>
Cancelled.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
title> This title is far too long to be accepted here
Keep the title to 40 characters.
title> Short title
priority (1 urgent, 2 high, 3 normal, 4 low)> 5
Type 1, 2, 3 or 4.
priority (1 urgent, 2 high, 3 normal, 4 low)> x
Type 1, 2, 3 or 4.
priority (1 urgent, 2 high, 3 normal, 4 low)>
Cancelled.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
title> Broken chair
priority (1 urgent, 2 high, 3 normal, 4 low)> 4
Opened #1 Broken chair (low): number 1 in line of 1.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 4
ticket> x
Type a ticket number, like 3 or #3.
ticket> #99
No ticket #99 is waiting.
ticket> 1
new priority (1 urgent, 2 high, 3 normal, 4 low)> 4
#1 is low already.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 4
ticket> #1
new priority (1 urgent, 2 high, 3 normal, 4 low)>
Cancelled.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 5
ticket to cancel>
Cancelled.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 7
Opened 8 sample tickets, #2 to #9.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 7
Opened 8 sample tickets, #10 to #17.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 7
Opened 8 sample tickets, #18 to #25.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 7
The sample would take the queue past 30 tickets.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
title> Extra one
priority (1 urgent, 2 high, 3 normal, 4 low)> 3
Opened #26 Extra one (normal): number 19 in line of 26.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
title> Extra two
priority (1 urgent, 2 high, 3 normal, 4 low)> 3
Opened #27 Extra two (normal): number 20 in line of 27.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
title> Extra three
priority (1 urgent, 2 high, 3 normal, 4 low)> 3
Opened #28 Extra three (normal): number 21 in line of 28.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
title> Extra four
priority (1 urgent, 2 high, 3 normal, 4 low)> 3
Opened #29 Extra four (normal): number 22 in line of 29.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
title> Extra five
priority (1 urgent, 2 high, 3 normal, 4 low)> 3
Opened #30 Extra five (normal): number 23 in line of 30.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
30 tickets are waiting, the most the queue holds - serve some first.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 6
priority waiting served
urgent 6 0 ######
high 6 0 ######
normal 11 0 ###########
low 7 0 #######
Waiting 30, served 0, next ticket number #31.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 8
Bye.
What was typed (50 lines)
0
x
2
3
4
5
6
1
1
This title is far too long to be accepted here
Short title
5
x
1
Broken chair
4
4
x
#99
1
4
4
#1
5
7
7
7
7
1
Extra one
3
1
Extra two
3
1
Extra three
3
1
Extra four
3
1
Extra five
3
1
6
8
basic
interpreter: byte-equal== Help desk ==
Tickets are served most urgent first, and in the order they came within a priority.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 7
Opened 8 sample tickets, #1 to #8.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 3
1. #3 Server room too warm (urgent)
2. #7 Payroll system down (urgent)
3. #2 Cannot log in to email (high)
4. #5 VPN drops every hour (high)
5. #4 New laptop for Maria (normal)
6. #8 Monitor flickers (normal)
7. #1 Printer out of toner (low)
8. #6 Update the wiki page (low)
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 2
Serving #3 Server room too warm (urgent). 7 tickets still waiting.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 2
Serving #7 Payroll system down (urgent). 6 tickets still waiting.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 4
ticket> 8
new priority (1 urgent, 2 high, 3 normal, 4 low)> 1
#8 Monitor flickers: normal -> urgent, now number 1 in line.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 5
ticket to cancel> #6
Cancelled #6 Update the wiki page (low). 5 tickets still waiting.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 1
title> Coffee machine leaks
priority (1 urgent, 2 high, 3 normal, 4 low)> 2
Opened #9 Coffee machine leaks (high): number 4 in line of 6.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 6
priority waiting served
urgent 1 2 #
high 3 0 ###
normal 1 0 #
low 1 0 #
Waiting 6, served 2, next ticket number #10.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 2
Serving #8 Monitor flickers (urgent). 5 tickets still waiting.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 2
Serving #2 Cannot log in to email (high). 4 tickets still waiting.
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 3
1. #5 VPN drops every hour (high)
2. #9 Coffee machine leaks (high)
3. #4 New laptop for Maria (normal)
4. #1 Printer out of toner (low)
1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit
choice> 8
Bye.
What was typed (17 lines)
7
3
2
2
4
8
1
5
#6
1
Coffee machine leaks
2
6
2
2
3
8
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P053 help-desk queue: open support tickets with a priority, serve them
# most urgent first and, within a priority, in the order they came in;
# change a waiting ticket's priority or cancel it, and see the queue grouped
# by priority.
import heap
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def level_name(p):
return ["urgent", "high", "normal", "low"][p - 1]
def counted(n, one, many):
if n == 1:
return "1 " + one
return str(n) + " " + many
def ticket(t):
return "#" + str(t[1]) + " " + t[2] + " (" + level_name(t[0]) + ")"
def place_in_line(q, number):
heap.service_order(q[0]) => order
for k in [0:len(order) - 1]:
if order[k][1] == number:
return k + 1
return 0
def ask_priority(prompt):
while True:
trim(input(prompt + " (1 urgent, 2 high, 3 normal, 4 low)> ")) => answer
if answer == "":
return 0
if answer == "1" or answer == "2" or answer == "3" or answer == "4":
return int(answer)
"Type 1, 2, 3 or 4." ^0
def ask_ticket(q, prompt):
# The index in the heap of a waiting ticket, or -1 when the answer is
# empty.
while True:
trim(input(prompt)) => answer
if answer == "":
return -1
if len(answer) > 1 and answer[0] == "#":
answer[1:len(answer)] => answer
True => digits
for c in answer:
if not (c >= "0" and c <= "9"):
False => digits
if answer != "" and digits and len(answer) < 6:
heap.find(q[0], int(answer)) => i
if i >= 0:
return i
("No ticket #" + answer + " is waiting.") ^0
else:
"Type a ticket number, like 3 or #3." ^0
def add(q, title, priority):
[priority, q[1], title] => t
q[1] + 1 => q[1]
heap.push(q[0], t) => q[0]
return t
def new_ticket(q):
if len(q[0]) == 30:
"30 tickets are waiting, the most the queue holds - serve some first." ^0
return
while True:
trim(input("title> ")) => title
if title == "":
"Cancelled." ^0
return
if len(title) <= 40:
break
"Keep the title to 40 characters." ^0
ask_priority("priority") => p
if p == 0:
"Cancelled." ^0
return
add(q, title, p) => t
("Opened " + ticket(t) + ": number " + str(place_in_line(q, t[1])) + " in line of " + str(len(q[0])) + ".") ^0
def serve(q):
if len(q[0]) == 0:
"No ticket is waiting." ^0
return
heap.pop(q[0]) => res
res[1] => q[0]
res[0] => t
q[2][t[0] - 1] + 1 => q[2][t[0] - 1]
("Serving " + ticket(t) + ". " + counted(len(q[0]), "ticket", "tickets") + " still waiting.") ^0
def waiting(q):
if len(q[0]) == 0:
"No ticket is waiting." ^0
return
heap.service_order(q[0]) => order
for k in [0:len(order) - 1]:
str(k + 1) => n
while len(n) < 3:
" " + n => n
(n + ". " + ticket(order[k])) ^0
def change(q):
if len(q[0]) == 0:
"No ticket is waiting." ^0
return
ask_ticket(q, "ticket> ") => i
if i == -1:
"Cancelled." ^0
return
q[0][i] => t
ask_priority("new priority") => p
if p == 0:
"Cancelled." ^0
return
if p == t[0]:
("#" + str(t[1]) + " is " + level_name(p) + " already.") ^0
return
level_name(t[0]) => was
heap.reprioritized(q[0], i, p)
("#" + str(t[1]) + " " + t[2] + ": " + was + " -> " + level_name(p) + ", now number " + str(place_in_line(q, t[1])) + " in line.") ^0
def cancel(q):
if len(q[0]) == 0:
"No ticket is waiting." ^0
return
ask_ticket(q, "ticket to cancel> ") => i
if i == -1:
"Cancelled." ^0
return
heap.removed_at(q[0], i) => res
res[1] => q[0]
("Cancelled " + ticket(res[0]) + ". " + counted(len(q[0]), "ticket", "tickets") + " still waiting.") ^0
def summary(q):
# Waiting tickets in one bucket per priority, as the corpus case
# task-priority-bucketer sorts tasks into buckets, and how many of each
# priority have been served.
[0, 0, 0, 0] => counts
for t in q[0]:
counts[t[0] - 1] + 1 => counts[t[0] - 1]
"priority waiting served" ^0
for p in [1:4]:
level_name(p) => name
while len(name) < 10:
name + " " => name
str(counts[p - 1]) => w
while len(w) < 7:
" " + w => w
str(q[2][p - 1]) => s
while len(s) < 8:
" " + s => s
name + w + s => line
if counts[p - 1] > 0:
line + " " + "#" * counts[p - 1] => line
line ^0
("Waiting " + str(len(q[0])) + ", served " + str(q[2][0] + q[2][1] + q[2][2] + q[2][3]) + ", next ticket number #" + str(q[1]) + ".") ^0
def sample(q):
for t in [["Printer out of toner", 4], ["Cannot log in to email", 2], ["Server room too warm", 1],
["New laptop for Maria", 3], ["VPN drops every hour", 2], ["Update the wiki page", 4],
["Payroll system down", 1], ["Monitor flickers", 3]]:
add(q, t[0], t[1])
"== Help desk ==" ^0
"Tickets are served most urgent first, and in the order they came within a priority." ^0
# [the heap, the next ticket number, served per priority]
[[], 1, [0, 0, 0, 0]] => q
True => running
while running:
"" ^0
"1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
new_ticket(q)
elif choice == "2":
serve(q)
elif choice == "3":
waiting(q)
elif choice == "4":
change(q)
elif choice == "5":
cancel(q)
elif choice == "6":
summary(q)
elif choice == "7":
if len(q[0]) + 8 > 30:
"The sample would take the queue past 30 tickets." ^0
else:
q[1] => first
sample(q)
("Opened 8 sample tickets, #" + str(first) + " to #" + str(q[1] - 1) + ".") ^0
elif choice == "8":
False => running
else:
"Pick a number from 1 to 8." ^0
"Bye." ^0
Python projection (main.py)
import heap
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def level_name(p):
return ["urgent", "high", "normal", "low"][p - 1]
def counted(n, one, many):
if n == 1:
return "1 " + one
return str(n) + " " + many
def ticket(t):
return "#" + str(t[1]) + " " + t[2] + " (" + level_name(t[0]) + ")"
def place_in_line(q, number):
order = heap.service_order(q[0])
for k in range(0, len(order)):
if order[k][1] == number:
return k + 1
return 0
def ask_priority(prompt):
while True:
answer = trim(input(prompt + " (1 urgent, 2 high, 3 normal, 4 low)> "))
if answer == "":
return 0
if answer == "1" or answer == "2" or answer == "3" or answer == "4":
return int(answer)
print("Type 1, 2, 3 or 4.")
def ask_ticket(q, prompt):
while True:
answer = trim(input(prompt))
if answer == "":
return -1
if len(answer) > 1 and answer[0] == "#":
answer = answer[1:len(answer)]
digits = True
for c in answer:
if not (c >= "0" and c <= "9"):
digits = False
if answer != "" and digits and len(answer) < 6:
i = heap.find(q[0], int(answer))
if i >= 0:
return i
print("No ticket #" + answer + " is waiting.")
else:
print("Type a ticket number, like 3 or #3.")
def add(q, title, priority):
t = [priority, q[1], title]
q[1] = q[1] + 1
q[0] = heap.push(q[0], t)
return t
def new_ticket(q):
if len(q[0]) == 30:
print("30 tickets are waiting, the most the queue holds - serve some first.")
return
while True:
title = trim(input("title> "))
if title == "":
print("Cancelled.")
return
if len(title) <= 40:
break
print("Keep the title to 40 characters.")
p = ask_priority("priority")
if p == 0:
print("Cancelled.")
return
t = add(q, title, p)
print("Opened " + ticket(t) + ": number " + str(place_in_line(q, t[1])) + " in line of " + str(len(q[0])) + ".")
def serve(q):
if len(q[0]) == 0:
print("No ticket is waiting.")
return
res = heap.pop(q[0])
q[0] = res[1]
t = res[0]
q[2][t[0] - 1] = q[2][t[0] - 1] + 1
print("Serving " + ticket(t) + ". " + counted(len(q[0]), "ticket", "tickets") + " still waiting.")
def waiting(q):
if len(q[0]) == 0:
print("No ticket is waiting.")
return
order = heap.service_order(q[0])
for k in range(0, len(order)):
n = str(k + 1)
while len(n) < 3:
n = " " + n
print(n + ". " + ticket(order[k]))
def change(q):
if len(q[0]) == 0:
print("No ticket is waiting.")
return
i = ask_ticket(q, "ticket> ")
if i == -1:
print("Cancelled.")
return
t = q[0][i]
p = ask_priority("new priority")
if p == 0:
print("Cancelled.")
return
if p == t[0]:
print("#" + str(t[1]) + " is " + level_name(p) + " already.")
return
was = level_name(t[0])
heap.reprioritized(q[0], i, p)
print("#" + str(t[1]) + " " + t[2] + ": " + was + " -> " + level_name(p) + ", now number " + str(place_in_line(q, t[1])) + " in line.")
def cancel(q):
if len(q[0]) == 0:
print("No ticket is waiting.")
return
i = ask_ticket(q, "ticket to cancel> ")
if i == -1:
print("Cancelled.")
return
res = heap.removed_at(q[0], i)
q[0] = res[1]
print("Cancelled " + ticket(res[0]) + ". " + counted(len(q[0]), "ticket", "tickets") + " still waiting.")
def summary(q):
counts = [0, 0, 0, 0]
for t in q[0]:
counts[t[0] - 1] = counts[t[0] - 1] + 1
print("priority waiting served")
for p in range(1, 5):
name = level_name(p)
while len(name) < 10:
name = name + " "
w = str(counts[p - 1])
while len(w) < 7:
w = " " + w
s = str(q[2][p - 1])
while len(s) < 8:
s = " " + s
line = name + w + s
if counts[p - 1] > 0:
line = line + " " + "#" * counts[p - 1]
print(line)
print("Waiting " + str(len(q[0])) + ", served " + str(q[2][0] + q[2][1] + q[2][2] + q[2][3]) + ", next ticket number #" + str(q[1]) + ".")
def sample(q):
for t in [["Printer out of toner", 4], ["Cannot log in to email", 2], ["Server room too warm", 1], ["New laptop for Maria", 3], ["VPN drops every hour", 2], ["Update the wiki page", 4], ["Payroll system down", 1], ["Monitor flickers", 3]]:
add(q, t[0], t[1])
print("== Help desk ==")
print("Tickets are served most urgent first, and in the order they came within a priority.")
q = [[], 1, [0, 0, 0, 0]]
running = True
while running:
print("")
print("1) new ticket 2) serve next 3) waiting 4) change priority 5) cancel 6) summary 7) sample 8) quit")
choice = trim(input("choice> "))
if choice == "1":
new_ticket(q)
elif choice == "2":
serve(q)
elif choice == "3":
waiting(q)
elif choice == "4":
change(q)
elif choice == "5":
cancel(q)
elif choice == "6":
summary(q)
elif choice == "7":
if len(q[0]) + 8 > 30:
print("The sample would take the queue past 30 tickets.")
else:
first = q[1]
sample(q)
print("Opened 8 sample tickets, #" + str(first) + " to #" + str(q[1] - 1) + ".")
elif choice == "8":
running = False
else:
print("Pick a number from 1 to 8.")
print("Bye.")
heap.eml
eml# P053 help-desk queue - the waiting tickets as a binary min-heap, the
# corpus case binary-heap's structure: no child pointers, the entry at index
# i has its children at 2i + 1 and 2i + 2. An entry is a ticket
# [priority, number, title]. One ticket comes before another when its
# priority is more urgent (a smaller number), or, at the same priority, when
# it was opened first (a smaller ticket number) - first come, first served
# within each priority.
def before(a, b):
return a[0] < b[0] or (a[0] == b[0] and a[1] < b[1])
def swap(h, i, j):
h[i] => t
h[j] => h[i]
t => h[j]
def sift_up(h, i):
while i > 0:
int((i - 1) / 2) => p
if not before(h[i], h[p]):
return
swap(h, i, p)
p => i
def sift_down(h, i):
len(h) => n
while True:
2 * i + 1 => l
l + 1 => r
i => m
if l < n and before(h[l], h[m]):
l => m
if r < n and before(h[r], h[m]):
r => m
if m == i:
return
swap(h, i, m)
m => i
def push(h, entry):
# Returns the heap with entry in it (the list grows by +, which makes a
# new list, so the caller keeps the returned one).
h + [entry] => h
sift_up(h, len(h) - 1)
return h
def removed_at(h, i):
# Returns [the entry at index i, the heap without it]. The last entry
# moves into the gap and sifts up or down - only one of the two moves it.
h[i] => out
h[len(h) - 1] => last
h[0:len(h) - 1] => h
if i < len(h):
last => h[i]
sift_up(h, i)
sift_down(h, i)
return [out, h]
def pop(h):
return removed_at(h, 0)
def find(h, number):
for i in [0:len(h) - 1]:
if h[i][1] == number:
return i
return -1
def reprioritized(h, i, priority):
priority => h[i][0]
sift_up(h, i)
sift_down(h, i)
def service_order(h):
# The waiting tickets in the order they will be served: popped one by one
# from a copy, so the queue itself is left alone.
h[0:len(h)] => c
[] => out
while len(c) > 0:
pop(c) => res
out + [res[0]] => out
res[1] => c
return out
Python projection (heap.py)
def before(a, b):
return a[0] < b[0] or a[0] == b[0] and a[1] < b[1]
def swap(h, i, j):
t = h[i]
h[i] = h[j]
h[j] = t
def sift_up(h, i):
while i > 0:
p = int((i - 1) / 2)
if not before(h[i], h[p]):
return
swap(h, i, p)
i = p
def sift_down(h, i):
n = len(h)
while True:
l = 2 * i + 1
r = l + 1
m = i
if l < n and before(h[l], h[m]):
m = l
if r < n and before(h[r], h[m]):
m = r
if m == i:
return
swap(h, i, m)
i = m
def push(h, entry):
h = h + [entry]
sift_up(h, len(h) - 1)
return h
def removed_at(h, i):
out = h[i]
last = h[len(h) - 1]
h = h[0:len(h) - 1]
if i < len(h):
h[i] = last
sift_up(h, i)
sift_down(h, i)
return [out, h]
def pop(h):
return removed_at(h, 0)
def find(h, number):
for i in range(0, len(h)):
if h[i][1] == number:
return i
return -1
def reprioritized(h, i, priority):
h[i][0] = priority
sift_up(h, i)
sift_down(h, i)
def service_order(h):
c = h[0:len(h)]
out = []
while len(c) > 0:
res = pop(c)
out = out + [res[0]]
c = res[1]
return out