Author: S. Loinjak
Date: 02:38:44 02/20/03
Go up one level in this thread
how about a reduced heap sort algorithm: 1) insert all entries in a sorted heap [can be implemented as array] (binary tree where all parents have higher priority than their 2 children - at the end the element with highest prio is on top [i.e. at first place in an array like heap]) costs: n*log(n) in worst case (where n is the number of current entries in the heap) 2) get the entry with highest prio from top of the heap (constant costs) and afterwards put the last element on the top of the heap and let it sink to the place where it belongs according to its priority now the heap property (parents have higher prio than children) is fullfilled again and you can get the next most important entry again from top of the heap costs: n*log*n Of course this method is only worth considering if you need several elements with highest (remaining) prio and not only the first one. <details: search for e.g. priority queues, heap, heapify, sink> --> http://www.onthenet.com.au/~grahamis/int2008/week11/lect11.html Sini P.S: I've used this method successfully in a queue simulation but also intend to use it in my chess engine if I'll ever write one.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.