Archive for October, 2010
An animation of adding elements to a heap
Here is an animation of how elements are inserted into a heap (sometimes used to implement a prioirty queue). At the top you can see the elements arranged in a tree, at the bottom is the corresponding array representation of the heap. The correspondence between the tree nodes and the array is such that the children of array element j are stored in positions 2j+1 and 2j+2 (where the indexing starts at 0).
The algorithm corresponds to what is described in section 4.3.2 of in “The Algorithm Design Manual” by Steven Skiena. Each time an element is added, it is put into the first empty position in the array representation at the bottom. This corresponds to making the new element a child of one of the leaf nodes. Then, the element is ‘bubbled up’ (swapped with its parent) as long as it is smaller than the parent.
Running the example requires Java Webstart (and is at your own risk, the author does not take any responsibility for any negative effects caused by running this example). To start the demo, click here. This demo makes use of the Trident java animation library.
Comments and suggestions are welcome !
Read Full Post | Make a Comment ( None so far )An animation of the Quicksort algorithm
Here is a (preliminary) animation of the Quicksort algorithm. At the same time, this is a small project to try out the Trident java animation library.
Running the example requires Java Webstart (and is at your own risk, the author does not take any responsibility for any negative effects caused by running this example). To start the demo, click here.
A few explanations:
- The example is modeled after the Quicksort implementation as given in “The Algorithm Design Manual” by Steven Skiena (Section 4.6)
- Those boxes which are already at the final position are drawn in white (instead of gray)
- The boxes with dark red background are those currently being worked on (between the variables l and h). The variables l and h themselves are shown by the boxes ‘L’ and ‘H’
- The variable i is displayed by the box I
- The pivot (against which the element at i is compared) is at position h in this implementation
- The box F corresponds to the value of the variable ‘firsthigh’ in Skiena’s book
You’ll notice that:
- after i reached the right end of the range currently being worked on (end of routine ‘partition’), the value originally at h will be put where ‘firsthigh’ is and is at its final position. The elements left of it (in the current range) will have a smaller value, the ones on the right a larger value.
Comments and suggestions are welcome !
Read Full Post | Make a Comment ( None so far )Filling a TNtuple in pyROOT
I recently came across the problem that I wanted to create a TNtuple with 635 variables. I wanted to avoid using a TTree if possible (how to do this is discussed here).
I found a solution in a tutorial (page 17) how to use fill a TNtuple with few variables (TNTuple currently has two Fill(..) methods: One taking up to 15 values and another one taking an array).
So the example in the tutorial did not work for me as I have more than 15 values per row. I managed to do this however with code similar to the following one:
import ROOT, array
# the variable names for the output tuple
varnames = [ ... ]
# open the output file
fout = ROOT.TFile("output.root", "RECREATE")
fout.cd()
# create the ntuple
output_tuple = ROOT.TNtuple("tuple","tuple",":".join(varnames))
# loop over events
...
# calculate the values to be stored in the output tuple
values = [ ... ]
# convert the list of values to an float array and fill the output tuple
output_tuple.Fill(array.array("f",values))
# end of loop over events
# write the tuple to the output file and close it
fout.cd()
output_tuple.Write()
Read Full Post | Make a Comment ( 5 so far )
Andre Holzner's Blog 