Inserting values into a sorted list, using binary sort.

Hello.

I haven’t seen such a handler here already, and I think it should be a tad faster, than concatenating two list, and running quickSort over the new list, since the list is sorted up front.

I have snagged Nigel Garveys binarySearchForClosestMatch match handler in order to do so. And StefanK’s orderdInsert handler, because that handler is what made me make binaryOrderedInsert. StefanK’s handler, should be used as long as there are less than 16 items in the list or so.

on orderedInsert(_list, _itemToInsert)
	-- http://macscripter.net/viewtopic.php?pid=178428
	-- StefanK
	set end of _list to _itemToInsert
	set i to count _list
	repeat while i > 1 and _itemToInsert < item (i - 1) of _list
		set item i of _list to item (i - 1) of _list
		set i to i - 1
	end repeat
	set item i of _list to _itemToInsert
	return i -- position of new item
end orderedInsert



on binarySearchForClosestMatch(theList, theKey)
	# Based on:
	# http://macscripter.net/viewtopic.php?id=41483
	# by: Nigel Garvey
	script o
		property lst : theList
	end script
	
	set l to 1
	set R to (count theList)
	
	repeat while (R > l + 1)
		set m to (l + R) div 2
		
		if (item m of o's lst < theKey) then
			set l to m
		else
			set R to m
		end if
	end repeat

	if class of theKey is integer or class of theKey is real then
		if (theKey - (item l of o's lst) > (item R of o's lst) - theKey) then
			return R
		else
			return l
		end if
	else if class of theKey is string then
		if theKey ≤ item l of o's lst then
			return l
		else if theKey ≤ item R of o's lst then
			return R
		else
			return (R + 1)
		end if
	end if
end binarySearchForClosestMatch

on binaryOrderedInsert(theList, newItem)
	-- http://macscripter.net/viewtopic.php?pid=178453#p178453
	script o
		property lst : theList
	end script
	
	set ix to my binarySearchForClosestMatch(o's lst, newItem)
	if ix is 1 then
		if newItem < item 1 of o's lst then
			set nl to {newItem} & o's lst
		else
			set nl to {item 1 of o's lst} & {newItem} & items 2 thru -1 of o's lst
		end if
	else if ix < (count o's lst) then
		if newItem < item ix of o's lst then
			set nl to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
		else
			set nl to items 1 thru ix of o's lst & {newItem} & items (ix + 1) thru -1 of o's lst
		end if
	else
		if newItem < item -1 of o's lst then
			set nl to items 1 thru -2 of o's lst & {newItem} & {item -1 of o's lst}
		else
			set nl to o's lst & {newItem}
		end if
	end if
	return nl
end binaryOrderedInsert

Edit
I have removed a bug, which was testing for class = number, when the correct is to test for class = integer or class = real.

Thanks to Nigel Garvey.

Edit2

There was a another bug here as well, when concatenating the list when the new item, was bigger than the last item in the list.

Hello.

I modified Nigels ClosestBinaryMatch handler, to work with strings as well as numbers, because I strings is really what I want to use it for at the moment. :slight_smile:

Hi McUsrII.

Stefan’s and your processes are essentially the last repeat in an insertion sort, with all but the last value having been sorted already and the last value being added to the list just before being sorted. Stefan’s is an in-place sort; yours uses a binary-search for speed and returns a different list from the one which went in. It’s also class dependent [] and errors if the list starts off empty. [i][ Your check for the class of theKey being ‘number’ always returns ‘false’. A number’s class is either ‘integer’ or ‘real’.][/i]

Another, possibly unimportant difference is that a standard insertion sort is “stable”. A value coming in from the right is inserted to the right of any values which are equal to it and so equal values remain in the original order with respect to each other. Since a binary search searches from both ends of the target range, it has to be weighted so that the right index remains to the right of any values which are equal to the one being inserted ” if you want a “stable” insertion, that is. (It’s a good idea anyway in an in-place sort, because fewer values then need to be shifted make room for the insertion.) Your binary search sets R to m if item m is greater than or equal to theKey, so it could place the insertion point to the left of an equal value.

Here’s a stable in-place version adapted from my own binary-search insertion sort:


on binaryOrderedInsert(theList, v)
	script o
		property lst : theList
	end script
	
	set end of o's lst to v
	set len to (count theList)
	
	-- Binary search for a "stable" insertion point (ie. after any similar values).
	set l to 1
	set here to len
	repeat until (l = here)
		set m to (l + here) div 2
		if (item m of o's lst > v) then
			-- Reduce the right index only if item m's value is GREATER than v.
			set here to m
		else
			-- Otherwise advance the left.
			set l to m + 1
		end if
	end repeat
	
	-- Shift the values to the right of the insertion point.
	repeat with i from len - 1 to here by -1
		set item (i + 1) of o's lst to item i of o's lst
	end repeat
	-- Insert the new value.
	set item here of o's lst to v
	
	return -- nothing.
end binaryOrderedInsert

set lst to {}
repeat with i from 1 to 1000
	set end of my lst to i
end repeat

binaryOrderedInsert(lst, 0)
lst

The binary search idea allows an interesting development in that, if the insertion point’s identified as being in the left half of the list, the insertion can be done from that end instead, reducing the number of values which have to be moved out of the way:


on binaryOrderedInsert(theList, v)
	script o
		property lst : theList
	end script
	
	set len to (count theList) + 1 -- What the list's length will be after the new value's added.
	
	-- Binary search for a "stable" insertion point (ie. AFTER any similar values).
	set l to 1
	set here to len
	repeat until (l = here)
		set m to (l + here) div 2
		if (item m of o's lst > v) then
			-- Reduce the right index only if item m's value is GREATER than v.
			set here to m
		else
			-- Otherwise advance the left.
			set l to m + 1
		end if
	end repeat
	
	-- Insert from the end of the list containing the insertion point.
	if (here > len div 2) then
		-- Insertion point in right half. Append the new value to the end of the list.
		set end of o's lst to v
		-- Shift the intervening values to the right.
		repeat with i from len - 1 to here by -1
			set item (i + 1) of o's lst to item i of o's lst
		end repeat
	else
		-- Insertion point in left half. Append the new value to the beginning of the list.
		set beginning of o's lst to v
		-- Shift the intervening values to the left.
		repeat with i from 2 to here
			set item (i - 1) of o's lst to item i of o's lst
		end repeat
	end if
	-- Insert the new value.
	set item here of o's lst to v
	
	return -- nothing.
end binaryOrderedInsert

set lst to {}
repeat with i from 1 to 1000
	set end of my lst to i
end repeat

binaryOrderedInsert(lst, 0)
lst

Hello.

You have made some nice handlers there

Thanks for the heads up on the fact that class has to be integer, and real. I have fixed that. When it comes to the checking for an empty list, then I am not sure, if it is wise, since I follow a convention of checking preconditons before I call a handler.

I didn’t worry to much about stable, only that the items should come along in right order, I figured I’d reuse the closest match handler, and it is problematic for it to return a stable match, and so the problem permeats into the binaryOrderedInsert handler, if the list consists of non-unique values.

I am quite perplexed, over how fast the shifting of elements in your handlers are done. Your handlers isn’t that much faster than what I came up with though. The average difference is 2 milliseconds faster, on 15000 elements. (I inserted129, so there is a lot of shifting going on. :), but my unstable version becomes faster, when the element to insert is more of in the middle of the list, in those unrealistically large lists.

Your second handler is 1 millisec faster on the average when the element was 0. If the element to insert was 4500, then your handler seemed to be around 6 millseconds slower, (the list contained 10000 elements).

So, at some point, the shifting is slower than concatenating, but the number of elements in the list, is far higher than I anything I presume I am going to need. So, a stable version, and just one handler, is a way better alternative. Thanks. :slight_smile:

Hello NIgel.

I scavenged your binaryOrderedInsert, into a binaryInsPos, and combined it with my insertion handler, that I have rewrote, based on the fact that binaryInsPos() is stable.

I am very pleased with the result. It performs well on the average.

on binaryInsPos(theList, v)
	# Based on Nigel Garvey's BinaryOrdered Insert,
	# since it delivers a stable positioning.
	script o
		property lst : theList
	end script
	
	-- set end of o's lst to v
	set len to (count theList)
	
	-- Binary search for a "stable" insertion point (ie. after any similar values).
	set l to 1
	set here to (len + 1)
	repeat until (l = here)
		set m to (l + here) div 2
		if (item m of o's lst > v) then
			-- Reduce the right index only if item m's value is GREATER than v.
			set here to m
		else
			-- Otherwise advance the left.
			set l to m + 1
		end if
	end repeat
	return here
end binaryInsPos

on binaryOrderedInsert(theList, newItem)
	-- http://macscripter.net/viewtopic.php?pid=178453#p178453
	script o
		property lst : theList
	end script
	
	if theList is {} then
		return {newItem}
	end if
	
	set ix to my binaryInsPos(o's lst, newItem)
	
	if ix is 1 then
		set NL to {newItem} & o's lst
	else if ix ≤ (count o's lst) then
		set NL to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
	else
		set NL to o's lst & {newItem}
	end if
	
	return NL
end binaryOrderedInsert



In my original, it’s the ‘here’ variable which goes on to indicate the insertion point, as in “The insertion point is here.” It doesn’t matter technically, of course, because the exit from the search is when ‘l’ and ‘here’ are the same, but it’s a bit perverse to call one of the variables ‘here’ and then return the other one! :lol:

Hello.

My binaryOrderedInsert, now works a little bit better, because I removed anything from it, that could indicate that you wouldn’t have to use the return value. And, the binaryInsPos, now returns here, and not l. :slight_smile:

Hello Nigel.

Having given this a little more thought, especially with regards to realistic sizes of lists. I doubt I’ll ever need something more than say 500 items, at least as long as I deal with the kinds of data I can extract from the OS, with AppleScript.

As long as that assumption holds, I think your second handler is the best, but it should return the “here” value, so that one can update related lists, (one to one relations), using the already found position. for insertion. And then use some handler, that delivers the list, the pos, and the item, and returns a new list. :slight_smile:

Ah. Good idea! The return of nothing was a hangover from the sort from which the handler was adapted.

PS. By the way, I was thinking earlier today that a better way to compare the speeds of the various methods would be to see how long they take to build up a list of a certain length rather than how long they take to add one item to a list of a certain length. That should give a good idea of average performance. Generate a list of random numbers and see how long it takes each method to append items from that to its own, initially empty, test list.

Just for interest, I’ve also tried appending items to a list arranged as a heap rather than as a straight line, but there doesn’t seem to be any advantage. And progressing though the heaped items in order would be a bit of a performance!

Hello Nigel.

Let me say first of all, that at least my intended usage for binaryInsertionSort, is working with presorted lists, there is much more to gain, from using quicksort, or your stable sort, to sort the list before any elements are inserted. -But then it is rather nifty, to be able to insert an element or two at the correct position, and even update related lists.

It could be interesting to try to figure out the sweet spot with regards to peformance on a different number of elements, and using a common random number sequence. For the tests, between your and my take on the problem.

The heapSort algorithm would be interesting to see, but I can’t see any use for it, in AppleScript directly, a priorityQueue could be an interesting tool, if the need ever arises, huffman encoding isn’t practical from AppleScript either.

By the way: The sort command that comes with the shell, is capable of doing topological sorts (like traversing a graph, or tree), so people are using it for sorting todo’s and the like out there. :slight_smile:

Edit

I think I now have understood what you were getting at. :slight_smile: The binaryInsertionSort, uses the same number of comparisions, as you would, to insert a node in an unbalanced tree, which if memory is correct, is the underlying structure of a heap. I would be easy to traverse, it would be efficient, for both insertion, and lookup.
The deletion of an element, would be the inverse of an insertion, so that is efficient as well. A change of an element would require a deletion and an insertion.

We could probably make an ubalanced tree work, as a datastructure for sorting in AppleScript, but I’m not sure if it would be practically feasible, first and foremost, because of the complexity needed to implement it. But it could be a challenge. I’m not sure if there is any utility of it though, given the lengths of the lists, at least I operate on. It would maybe shave off a millsecond or two with those numbers of elements… It is not much of a gain. The other point against it, is that we are served most of our items in chunks, I believe it is faster to sort those chunks up front, if we don’t get the chunks presorted somehow. So, heapsorting a pre-fabricated chunk of items, doesn’t sound very efficient to me, (compared to quick/stable sort).

I am not going for implementing a heapsort, that is the conclusion, not now anyways, I don’t see any “bang for the buck” in it.

Actually
Having said that, it is also a pity that the stackspace in AppleScript is so scarce, so you can’t rely on recursion, to maintain the heap. That is one factor that complicates matters. You’d also probably need to use a list with three items for a node so the overall structure can become large given the structure around each item. That is another limiting factor, (The max number of actual items can’t greater than 4-5000, if the max number of elements is stil 2^14 items).

Quicksort is N log N on the average, so HeapSort is 2N log N on the average. Having read up a little, I remember that we simulated trees with arrays (Lecture 10 - Implementing a Tree in an Array), which is perfectly doable with AppleScript’s lists, it is even quite easy to grow the lists in either direction, where you simulate a tree with a simulated array. :smiley: You can get a perceived speed advantage, if the data lends itself to it, as time consumption for sorting, are acquired each time something is inserted, if using something like a priortiy queue, which a user won’t perceive as easily as one big list being sorted, which may become noticeable, as the sorting may stall a script or applet for some small amount of time, without the user fully understanding what is happening behind the scenes.

Hello.

I implemented a priority queue, and used it for sorting, just as a theoretical excercise. It is really just an implementation of how a priority queue works, in the simplest possible way. :slight_smile:

script pQueue
	property parent : AppleScript
	property beholder : {}
		
	on insert(pItem)
		set beginning of my beholder to pItem
	end insert
	
	on remove()
		set lcount to count my beholder
		if lcount is 0 then
			return missing value
		else
			set maxItem to item 1 of my beholder
			set tag to 1
			if lcount = 1 then
				set my beholder to {}
			else
				repeat with i from 2 to lcount
					if item i of my beholder > maxItem then
						set maxItem to item i of my beholder
						set tag to i
					end if
				end repeat
			end if
			if tag = 1 then
				set my beholder to rest of my beholder
			else if tag < lcount then
				set my beholder to items 1 thru (tag - 1) of my beholder & items (tag + 1) thru -1 of my beholder
			else
				set my beholder to items 1 thru -2 of my beholder
			end if
			return maxItem
		end if
	end remove
end script

set sorted to {}

repeat with i in {9, 4, 1, 19, 24, 93, 45}
	pQueue's insert(i)
end repeat

set resItem to {}

repeat while resItem is not missing value
	set resItem to pQueue's remove()
	if resItem is not missing value then
		set beginning of sorted to resItem
	end if
end repeat
log sorted
-- > (*1, 4, 9, 19, 24, 45, 93*)

Hello.

Ok, so I sat down, and wanted to implememt the heap for the priorityQueue with AppleScript, and then I realized, that the binaryInsertionSort, really is an as efficient method/datastructure for implementing a heap in AppleScript, as it can be. :slight_smile:

Hi McUsrII.

Looking again at your script in post #5:

  1. In the binaryInsPos() handler, since the new item’s not added to the list there, ‘here’ should been initialised to len + 1 in case the new item has to go on the end.
  2. In binaryOrderedInsert() handler, ‘else if ix < (count o’s lst) then’ should be ‘else if ix ≤ (count o’s lst) then’.
  3. binaryOrderedInsert() should return NL.

The following handler’s just for the hell of it. I doubt it has many advantages! :slight_smile:


on ternaryInsPos(theList, v)
	script o
		property lst : theList
	end script
	
	-- The insertion point will be somewhere between item 1 and after the last item.
	set l to 1
	set here to (count theList) + 1
	
	-- Ternary search for a "stable" insertion point (ie. after any similar values).
	repeat until (l = here)
		-- m is here a third-of range marker rather than a middle-of-range one.
		set m to l + (here - l) div 3
		if (item m of o's lst > v) then
			-- Reduce the right index only if item m's value is GREATER than v.
			set here to m
		else
			-- Otherwise advance the left and third-of-range indices and try again.
			set l to m
			set m to (l + here) div 2
			if (item m of o's lst > v) then
				-- Reduce the right index only if item m's value is GREATER than v.
				set here to m
			else
				-- Otherwise advance the left.
				set l to m + 1
			end if
		end if
	end repeat
	
	return here
end ternaryInsPos

Hello Nigel.

I have corrected the handlers in post #5, thanks for spotting the bugs.

I haven’t looked at your ternaryInsertionSort but I will. I think its for specialized usage. :slight_smile:

I hope I get time to implement a priority Queue, I have figured out before long, so spotting the culprits came in really handy at this stage.

Hi McUsrII.

binaryOrderedInsert()'s still returning the original list, not the concatenation result.

My ternary handler in post #13 also had an indexing problem when insertion points occurred at the ends of lists of certain lengths. I think it’s now fixed. As I hinted earlier, it’s just for fun. It appears on average to be slower than the binary version, having usually to test more items from the list.

Sorry for the sloppiness, I am in the middle of something.

Algorithms are fun. :slight_smile: I have to sit down and investigate your ternary sort a little. Now, a ternary search, as known from Alogrithm books, works over a range That hopefully only contains one extremal value. (Like the Newton Raphson method.) Now, you have bypassed that problem, since your range is sorted to begin with.

I’d say it could be used to fill in more values correctly, say if you miss point, and interpolate values, and then use your sort method so theey come in correct order before using the points to draw a graph or something. :slight_smile:

On the other side of the extremal value, you’ll have to reverse the result of course.

Just one usage, I came to think of.

This is for simulating a heap inside a priority queues, if the priorites,
are increasing with the value.

Priority queues are good for simulating stuff. Where you may have listeners
and writers, or both to the queue, and maybe uses a dispatcher, for sending
the event with the highest priority to the right receiver/observers.

The handler below, is totally scavenged from Nigel Garvey’s binaryInsPos, and its
intended usage is for when the values increases with the priority. This handler
is also “stable” which it needs to be, since I will use it too, as the basis
of a priority queue, which treats events with equal priorities in chronological
order.

Many places, priorities are made up the other way around, where a lower number
signifies a higher priority, then Nigels binaryInsPos is the best to use.

The principle of using a binarySearch based algorithm for inserting new values
in an already sorted list is effectively is, a practical implementation of a
“heap” in Applescript. It however only a partially acceptable situation,
but the overhead/gain,is hard to measure, or at least complicated. The thing
is, a real heap uses a binary complete tree. That’s a lot of overhead
in AppleScript! Real applications often uses arrays to simulate binary
complete trees, especially if they are residing in a kernel, and wants to
avoid memory leaks.

Thus, in order to use a binary complete tree in AppleScript, we may implement it
by simulating a tree by an array, it is just that we don’t have arrays,
so we’ll have to simulate the array as well. The alternative is to
use a “real” node structure, this means that for every value we’ll need to
have a record, with four values, that we’ll have to book-keep. (I see
no other way of implementing the “upheap” routine, that balances the tree.)

  • We need to keep track of the parent node, in order to balance the tree, and
    we need to have room for to new childnodes. Every node has to be created, as
    new values are inserted and that operation isn’t as cheap, as in languages
    that support memory allocation -on the heap! We’ll have to use a handler
    for it. The priority queue that uses the “heap”, is quite efficient, in that
    you just remove the top item, and return the value, like a stack. A priority
    queue can be viewed as the common ancestor of both a stack and a queue.

Given all of the above I purport that using a binaryInsPos, is the best way
to implement a priorityQueue with AppleScript, even though the cost of inserting
elements are drastically higher than in a “real heap”, -where that cost is 2logN (log(2)N)
it is here N-1 in the worst case.

But then again, we don’t use priority queues that much in AppleScript.

It is mostly for fun, to simulate what the coffee maker says, when the customer
spills the coffee into the cash register. (That should be an event with high priority.) :wink:


on rBinaryInsPos(theList, v)
	# Based on Nigel Garvey's BinaryOrdered Insert,
	# since it delivers a stable positioning.
	script o
		property lst : theList
	end script
	
	-- set end of o's lst to v
	set len to (count theList)
	
	-- Binary search for a "stable" insertion point (ie. after any similar values).
	set l to 1
	set r to (len + 1)
	repeat until (l = r)
		set m to (l + r) div 2
		if (item m of o's lst < v) then
			-- Reduce the right index only if item m's value is LESSER than v.
			set r to m
		else
			-- Otherwise advance the left.
			set l to m + 1
		end if
	end repeat
	return r
end rBinaryInsPos

on rBinaryOrderedInsert(theList, newItem)
	-- http://macscripter.net/viewtopic.php?pid=178453#p178453
	script o
		property lst : theList
	end script
	
	if theList is {} then
		return {newItem}
	end if
	
	set ix to my rBinaryInsPos(o's lst, newItem)
	
	if ix is 1 then
		set NL to {newItem} & o's lst
	else if ix ≤ (count o's lst) then
		set NL to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
	else
		set NL to o's lst & {newItem}
	end if
	
	return NL
end rBinaryOrderedInsert

Edit
Changed a fact: the cost of insertion at least for some circumstances is around 2LogN for a “real” heap, not logN. (first locate the element which is logN (downheap), then insert it somewhere else (upheap) which is also LogN.
LogN means the base 2 logarithm of N. Log(2)N

Hello.

Here is a practical implementation of a priority queue. What’s interesting with it apart from it being a proper priority queue, is that it exceeds the specifications, thanks to Nigel’s work on the binary insertion sort handlers, which he made to be stable. Also great thanks to StefanK, that gave me the idea in the first place.

It takes records as values, and the records need to have a priority property.

The one unusal call to describe further here, is the replace() call, if the priority queue is made to be descending, and the item you want to replace has a greater priority than the item on top of the list, then that item is just returned.
if the list is ascending, then an item with lower priority is returned immediately, otherwise the top item is returned.

look() returns the top of the priority queue. remove() returns the top of the priority queue, and removes it. insert(v) inserts one, at its correct place according to its priority.

empty() tells if the priority queue is empty.

on newPriQueue(isDescending)
	-- Copyright © 2015 Nigel Garvey and  McUsr, all faults are McUsr's.
	-- you may not publish this on the web or in print as your own work, but please
	-- refer to this link: http://macscripter.net/viewtopic.php?pid=178453#p178453
	--	Creates either a descending or ascending priority queue.
	-- Uses in every practical sense a heap datastructure.
	-- the priorityQueue needs 
	--Modify it to suit your needs.
	-- Sedgewick 2end Ed. p 146
	script pq
		property _pqList : {}
		property descending : isDescending
		
		on rBinaryOrderedInsert(theList, newItem)
			-- http://macscripter.net/viewtopic.php?pid=178453#p178453
			script o
				property lst : theList
			end script
			
			if theList is {} then
				return {newItem}
			end if
			
			set ix to my rBinaryInsPos(o's lst, newItem)
			
			if ix is 1 then
				set NL to {newItem} & o's lst
			else if ix ≤ (count o's lst) then
				set NL to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
			else
				set NL to o's lst & {newItem}
			end if
			
			return NL
		end rBinaryOrderedInsert
		
		on rBinaryInsPos(theList, v)
			# Based on Nigel Garvey's BinaryOrdered Insert,
			# since it delivers a stable positioning.
			script o
				property lst : theList
			end script
			
			-- set end of o's lst to v
			set len to (count theList)
			
			-- Binary search for a "stable" insertion point (ie. after any similar values).
			set l to 1
			set r to (len + 1)
			repeat until (l = r)
				set m to (l + r) div 2
				if (|priority| of item m of o's lst < |priority| of v) then
					-- Reduce the right index only if item m's value is LESSER than v.
					set r to m
				else
					-- Otherwise advance the left.
					set l to m + 1
				end if
			end repeat
			return r
		end rBinaryInsPos
		
		
		on binaryInsPos(theList, v)
			# Based on Nigel Garvey's BinaryOrdered Insert,
			# since it delivers a stable positioning.
			script o
				property lst : theList
			end script
			
			-- set end of o's lst to v
			set len to (count theList)
			
			-- Binary search for a "stable" insertion point (ie. after any similar values).
			set l to 1
			set here to (len + 1)
			repeat until (l = here)
				set m to (l + here) div 2
				if (|priority| of item m of o's lst > |priority| of v) then
					-- Reduce the right index only if item m's value is GREATER than v.
					set here to m
				else
					-- Otherwise advance the left.
					set l to m + 1
				end if
			end repeat
			return here
		end binaryInsPos
		
		on binaryOrderedInsert(theList, newItem)
			-- http://macscripter.net/viewtopic.php?pid=178453#p178453
			script o
				property lst : theList
			end script
			
			if theList is {} then
				return {newItem}
			end if
			
			set ix to my binaryInsPos(o's lst, newItem)
			
			if ix is 1 then
				set NL to {newItem} & o's lst
			else if ix ≤ (count o's lst) then
				set NL to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
			else
				set NL to o's lst & {newItem}
			end if
			
			return NL
		end binaryOrderedInsert
		
		
		(* The implementation of the Abstract datastructure Priority queue *)
		
		on insert(v)
			-- WAS tested 2015-4-24
			if class of (|priority| of v) is not integer then error "insert(): only integers are accepted as input to  this priority queue!"
			if my descending then
				set my _pqList to rBinaryOrderedInsert(my _pqList, v)
			else
				_pqList of me to binaryOrderedInsert(my _pqList, v)
			end if
		end insert
		
		on remove()
			-- WAS tested 2015-4-24
			-- returns the largest element of the priority queue
			set pqllen to length of my _pqList
			if pqllen is 0 then return null
			set v to item 1 of my _pqList
			set my _pqList to rest of my _pqList
			return v
		end remove
		
		on replace(u)
			-- tested 2015-4-24
			set v to look()
			-- replaces the largest/smallest  item (descending/ascending)
			-- if the new item is lesser / bigger.
			if my descending then
				if |priority| of u < |priority| of v then
					remove()
					insert(u)
					return v
				else
					return u
				end if
			else
				if |priority| of u > |priority| of v then
					remove()
					insert(u)
					return v
				else
					return u
				end if
			end if
		end replace
		
		on look()
			if length of my _queueList is 0 then return null
			return item 1 of my _queueList
		end look
		
		--	change the priority of an item
		-- no can do, since we don't take data with us.
		-- so there is no priority to change.
		-- The way to do it, is to get at the item.
		-- thru binary search.
		-- then delete it, so we get it out,
		-- give it new priority, and 
		-- insert it back in.
		
		on empty()
			return my _pqList = {}
		end empty
	end script
end newPriQueue

Edit

Removed: deleteItemNr() deletes a specific item number from the priority queue, because it has nothing to do there, really.

2015-04-28 19:00 CET: Added “bars” or “pipes” around the property priority, “manually”, so they are compiled into the code, they may then just disappear, but that is perfectly fine. (Thanks to StefanK and DJ Bazzie Wazzie)

Hello.

This is a fully working minimum priority queue, that is, a priority queue, where the lesser priority is the most significant, -gets out of the priority queue fastest.

The records fed to the queue needs to have the fields |priority| and |key|. It is not optimized in any way, with regards to inlining of calls. And it wouldn’t be so easily implemented, hadn’t it been for the insights of Nigel Garvey. Thanks.

If you want a priority queue of descending order, and don’t have the patience for me to come around to it, then feel free to do so yourself. :slight_smile:

on newMinPqueue()
	script content
		(*
		Implemented by McUsr in Applescript, with the help of contributions by Nigel Garvey.
		Original API description found in Sedgewick Algorithms 2nd. edition.
		*)
		property _pqList : {}
		
		(* Internal handlers *)
		
		on _binaryInsPos(theList, v)
			# Based on Nigel Garvey's BinaryOrdered Insert,
			# since it delivers a stable positioning. This handler only considers |priority|
			# whereas the binaryDelPos must consider |key| as well.
			
			script o
				property lst : theList
			end script
			
			set len to (count theList)
			
			-- Binary search for a "stable" insertion point (ie. after any similar values).
			set l to 1
			set here to (len + 1)
			repeat until (l = here)
				set m to (l + here) div 2
				if priority of item m of o's lst > priority of v then
					-- Reduce the right index only if item m's value is GREATER than v.
					set here to m
				else
					-- Otherwise advance the left.
					set l to m + 1
				end if
			end repeat
			return here
		end _binaryInsPos
		
		(*

	Assumptions, there can just be one combination of the same key and the same priority in the priority queue
	in one single instance of time. Said in a different way: there can be no equal pairs in the priority queue
	Example: {|priority|:5,|key|:10} can't be inserted, if the item already exists.
	
	It is your responsibility, to see to, that this doesn't happen.
*)
		
		on _binaryDelPos(theList, v)
			-- Based on Nigel Garvey's BinaryOrdered Insert,
			-- since it delivers a stable positioning. -Its inlined for speed!
			-- After being put behind last item with that priority in the queue,
			-- we scan forward one by one, until we find the one, or not, with "our" key.
			script o
				property lst : theList
			end script
			set len to (count theList)
			-- Binary search for a "stable" insertion point (ie. after any similar values).
			set l to 1
			set r to (len + 1)
			repeat until (l = r)
				set m to (l + r) div 2
				if (priority of item m of o's lst > priority of v) then
					-- Reduce the right index only if item m's value is LESSER than v.
					set r to m
				else
					-- Otherwise advance the left.
					set l to m + 1
				end if
			end repeat
			set found to false
			
			set start to (r - 1)
			-- this is the "last" item, (closest to the end) with that priority
			-- from here on after, we must see if we can find a record with the 
			-- same key, while the priority doesn't change "upwards" in the priority queue.
			repeat with i from start to 1 by -1
				
				if priority of item i of o's lst = priority of v then
					if |key| of item i of o's lst = |key| of v then
						set r to r - (start - i + 1)
						-- There can be only one!
						set found to true
						exit repeat
					end if
				else
					exit repeat
				end if
			end repeat
			if not found then
				return 0
			else
				return r
			end if
		end _binaryDelPos
		
		on _deleteItemNr(ix)
			if ix > length of my _pqList then return null
			set i to item ix of my _pqList
			if ix is 1 then
				set my _pqList to rest of my _pqList
			else if ix < length of my _pqList then
				set my _pqList to items 1 thru (ix - 1) of my _pqList & items (ix + 1) thru -1 of my _pqList
			else
				set my _pqList to items 1 thru -2 of my _pqList
			end if
			return i
		end _deleteItemNr
		
		(* The API *)
		
		on pqinsert(v)
			-- inserts an item into the queue, according to its priority.
			-- Relies on _binaryInsPos, with internals by Nigel Garvey.
			-- http://macscripter.net/viewtopic.php?pid=178453#p178453
			if my _pqList is {} then
				set end of my _pqList to v
			else
				set ix to my _binaryInsPos(my _pqList, v)
				
				if ix is 1 then
					set my _pqList to {v} & my _pqList
				else if ix ≤ (count my _pqList) then
					set my _pqList to items 1 thru (ix - 1) of my _pqList & {v} & items ix thru -1 of my _pqList
				else
					set my _pqList to my _pqList & {v}
				end if
			end if
		end pqinsert
		
		on pqremove()
			-- returns the element of the priority queue with the lowest priority (pop()).
			set pqllen to length of my _pqList
			if pqllen is 0 then return null
			set v to item 1 of my _pqList
			set my _pqList to rest of my _pqList
			return v
		end pqremove
		
		on pqreplace(v)
			-- replaces the smallest  item (ascending priority queue)  with the new item,
			-- unless  the new item is lesser, returns the item that aren't staying in
			-- the priority queue.
			-- Opposite of:"Replace largest with new item, unless the new item is larger."
			set u to pqlook()
			if priority of v > priority of u then
				pqremove()
				pqinsert(v)
				return u
			else
				return v
			end if
		end pqreplace
		
		on pqempty()
			return my _pqList = {}
		end pqempty
		
		
		on pqlook()
			-- returns a peek of the next item that 
			-- is to be removed from the priority queue
			if length of my _pqList is 0 then return null
			-- The priority queue starts at the top.
			return item 1 of my _pqList
		end pqlook
		
		on pqchange(v, pri)
			--Change the priority of an arbitrary item.
			-- returns the item, whether the priority was changed or not.
			set foundPos to my _binaryDelPos(my _pqList, v)
			if foundPos > 0 then
				if priority of v ≠ pri then
					-- the pri wasn't the same, we'll have to remove it.
					my _deleteItemNr(foundPos)
					-- we update the priority
					set priority of v to pri
					-- and we insert it back
					pqinsert(v)
				end if
				return v
			else
				error "pqchange: The item wasn't in the priority queue"
			end if
		end pqchange
		
		on pqdelete(v)
			-- delete an arbitrary specified item with the same |priority| and |key|.
			-- returns true upon success 
			set foundPos to my _binaryDelPos(my _pqList, v)
			if foundPos > 0 then
				_deleteItemNr(foundPos)
				return true
			else
				return false
			end if
		end pqdelete
		
		
		on pqupdate(v, pri)
			(*
				It sees to that a vertices priority is lowered if possible, (in an ascending priority queue)
				if the record is not there, then it is inserted with the lowest priority.
			
			*)
			-- find the position of u in the queue, if it is there . . . 
			set foundPos to my _binaryDelPos(my _pqList, v)
			if foundPos > 0 and priority of v = pri then
				return false
			else if foundPos > 0 then
				-- this is effectively the pqchange operation 
				-- it is inlined, for efficiency 
				-- 		log "prioritiy of v : " & priority of v
				if pri < priority of v then
					-- the priority of v  was larger, we'll have to remove it: Sedgewick p. 455
					my _deleteItemNr(foundPos)
					-- we update the priority
					set priority of v to pri
					-- and we insert it back
					pqinsert(v)
					-- and 
					return true
				else
					-- priority of v was lesser than pri
					return false
				end if
			else if foundPos = 0 then
				-- we blatantly update the  priority queue with the record, and the least priority (ascending queue).
				if pri < priority of v then set priority of v to pri
				pqinsert(v)
				return true
			else
				error "update(u, pri): Hull breached, logic error!"
			end if
		end pqupdate
		
		on textRec(v)
			-- convenience, if you want a record to appear after some
			-- text in a log statement! :)
			return "priority: " & priority of v & ", key: " & |key| of v
		end textRec
		
		on pqinitialize()
			set my _pqList to {}
		end pqinitialize
	end script
end newMinPqueue

Driver:

set minpq to makeNewMinPqueue()
repeat with i from 1 to 10 --  by -1
	minpq's pqinsert({priority:i, |key|:(character id (i + 64))})
end repeat
-- return my _pqList
set rc to {priority:3, |key|:"N"}
set i to minpq's pqreplace(rc)
log "replaced : record with :  " & minpq's textRec(i)
set delItem to minpq's _deleteItemNr(10)
set sc to {priority:2, |key|:"B"}
set ex to {priority:3, |key|:"O"}
minpq's pqinsert(ex)

set ex to minpq's pqlook()
minpq's pqupdate(ex, 2)
minpq's pqupdate(rc, 2)
minpq's pqupdate(rc, 4)
log "Thoroughly testing pqupdate:"
set lc to {priority:4, |key|:"Q"}
minpq's pqupdate(lc, 4)
minpq's pqchange(lc, 5)
set priority of delItem to 0
set y to minpq's pqreplace(delItem)
set newDelItem to {priority:9, |key|:"I"}
return minpq's pqdelete(newDelItem)

Edit

Added a pqinitialize handler, because this should be faster than “making” a new priority queue, and I changed the name of the “constructor” to newMinPqueue.