A Heap of Papers

By Bobby Neal Winters

The other day I was walking around in one of the buildings on campus that is used whenever construction is being done somewhere.  The whole building, in its way, reminds me of the Room of Requirement in the Harry Potter books.  Whenever someone needs space, there it is.

While there isn’t anyone housed there currently--at least I didn’t think there was--it is an interesting place to walk around in.  You look in the various rooms and find all sorts of antiquated equipment.  There old ditto machines, ancient computers, chalk boards and implements to aid in writing on chalkboards.  The latter would include on of those 5-pronged chalk holders music teachers use (or at least used to use) to draw the scale on a blackboard and a chalk-holding protractor for geometry teachers.

It is also full of smells.  There is the sweet smell of machine oil; there is the smell of copier fluid from the ditto machines; there is the smell of dust.

There is also silence, silence broken only by the  sound of my footfalls on the floor, which is a checkerboard of aged linoleum tile and bare concrete.  

But then to my surprise I heard what seemed to be muttering.

At first I thought it was in my head, but as I turned my ears from side to side I found it was stronger in the direction of a door at the opposite end of the hall. Interested in seeing who else was in the building, I followed the sound until I came to the door.  When I got there, I heard the muttering quite clearly.  I knocked on the door.

“Hello,” I said as my knuckles wrapped against the wood, dirtied by the sweat from the hands of many generations of student.

“Hum, ha, ah...ah...ah..come in,” stammered a voice from the other side.

Opening the door, at first a crack and then wider, I saw a thin man with hair the color of chalk.  His face was thin and wrinkled; his skin was as thin as rice paper; but his eyes were clear and his hands were steady.  Behind him was a stack of papers that he appeared to have just finished grading, as the copious red ink on the top paper had yet to try..

“Hello,” I said again.  “I didn’t think there was anyone else over here.  I don’t recall any faculty being officed over here currently.”

“Well,” he paused. “I am still here.  They told me I could stay until I got my last set of exams graded.  I just finished so I should be vacating the premises soon.  I just want to order the exams from high score to low score so that I can rank them.”

Looking at him and seeing how old he was and looking at his stack of papers and seeing how many there were, I offered to help.

He refused this offer, however, saying he had a device.

“A device?” I echoed quizzically,

“Yes, look here,” he said indicating the back wall of the office.

Looking at the spot indicated, I saw what I’d originally taken to be an odd sort of plant stand.  It was roughly triangular in shape with the narrow part at the top.  The top consisted of a single plate, suspended from the ceiling.  Below that plate were two separate plates; below each of them two more for a total of four on that level.

Going down each level, there were twice as many shelves as the level above.  This went on for five levels total.  There were a total of

1+ 2+4+ ... + 32= 63

plates altogether.

He began to place his papers on the device in the following odd sort of way.  He put the first paper on the top.  It had received a 64.  He next one, which had received the score of 63; he compared that to the 64 and as it was less he put on the plate hanging just below it to the left.  The next one would have gone to on the plate the right, but it had a score of 69; so he took the 64 and put it there and put the 69 at the top, where the 69 had been.

The next paper was poised to go on the extreme left plate of the third level from the top, but it was a 72.  He took the 63 from the plate above it and placed it in the left plate instead.  Then he checked the value of the paper in the plate above that one; it was a 69, so he put that in the recently empty plate and put the 72 in the top plate in its stead.

After seeing him go through his motions a few more times, I noted the following:  Every paper had a lower score than that of the plate just above it.  As a consequence of this, when a given step was finished--that is when a given paper had reached its final destination--the paper with the highest score so far occupied the top plate.

It didn’t take him too long to get all his papers into the device. At that point, I noted the high score was an 84.  I looked at it and noted that it was written in blue ink and bore the scent of something that had been copied using a ditto-master.

I didn’t have long to look, however, as he took that paper and laid it face down on his desk.  The top plate was now empty. He proceeded to take the rightmost paper from the bottom row and put it in the top plate.  He then looked at the two papers below and swapped it with the paper that had the higher score of those two.  Following the paper he’d brought up from below, he repeated this process, i.e. he switched it with the larger of the two papers below it.  When this could no longer be done, i.e. when it was larger than the two papers below it, he stopped.  

Each of the papers were positions so that their scores were larger than the scores of the papers in the plates below them. Therefore, the paper in the top plate again had the highest score.  He removed it, put it face down on the precious paper.  Then he repeated the process again and again until all of the papers were stacked face down, atop each other on his desk. When he turned his stack over, they were in order with the highest score on top and the lowest score on bottom.

The Technical Part (Those only interested in the story may scroll to the end)

What he had done with his papers is called a heap sort.  The condition of having all values stored in the relative positions as described in which each value larger than the two values below it is called a heap.  

The heapsort is typically taught in the context of computer science and the technical details of computing using pointers, arrays, subscripts, and so forth can get in the way of understanding what is, essentially, a fairly simple technique.  I admired how this fellow’s simple device made the concept clear.  Once the concept is clear, it is not difficult to proceed to the technical details of dealing with array subscripts etc.

The algorithm proceeds in two steps.  The first is the building of the heap in which the largest element is found.  The second is disassembling the heap and reordering the remainder until nothing is left and everything is ordered.

The heap has the general structure of what is called a complete binary tree.  A tree has nodes, which were the plates the the story above.  It is arranged from top to bottom with the top node, oddly enough, referred to as the root. Below it are two--this is where the binary comes in--nodes which are referred to as its children.  The root is their parent. Both of these nodes have two children.  They will be referred to as the left child and the right child in the obvious way. Each generation is a level.  Saying that it is complete is saying that every level but the last is completely filled.

Values are placed in the nodes in the manner described above preserving the property that the value in each node is at least as large as the values in the children nodes.  The left child and the right child don’t have to have any particular relationship to each other; they are simply each lower than the value in the parent node.

One cannot, of course, literally build a device like the one the professor had in the computer, but is is possible to build something that is functionally equivalent.  We can do this by imposing some structure on an array.  For those of you who don’t know, an array is an object in a programming language that is like a numbered mailbox.

The numbering on the left of the picture above indicates the index.  The empty space on the right indicates a place for the value to go.  If an array is called A, the value stored at the i-th spot of the array is A[i].  In the picture, I’ve numbered the array beginning with 1 as is done in the computing language R.  Most other computing languages begin the indexing with 0.

We capture the structure of the binary tree by letting the 2i-th position and the (2i+1)-st position be the children of the i-th position. Conversely, floor(i/2) is the parent position of i. (This must be modified slightly to work if your array’s index begins with 0.)  This structure is indicated in the figure below:

When you begins the process in creating a heap, thing about it as if your values are in an array. Begin at the top and start sliding down. Compare the value at each position with its parent’s value. Keep swapping it upwards until it is as high at it can go, and then proceed down to the next value doing the same there.  This is equivalent to the procedure described above, but less colorful in its description.

When the heap is created, the largest value is in A[1].

Thus ends the first part of the algorithm.

The second part is described as shoveling that largest value from the top, replacing it with the final value from the array, and then restoring the heap-ness to the remaining array.  This uses a function called appropriately heapify. The syntax is heapify(array, root) and it is called recursively.  

When we remove the value A[1] and replace it with the final value stored in the array, it does destroy the heap-ness of the array.  However, if you consider the children of the root as being roots of their own trees, those trees are heaps themselves. Heapify will swap the new value at the root with the largest of its two children, check if the value is larger than both of its children in its new position. If so, we have a heap and stop; otherwise it will call itself with its new position as root, and so on until we have a heap.

Now we are back

All of this went through my head in the moment it took him to turn his papers over.  When he did, I happened to see the name of the top score of the paper.  It was the same name of the retired chair of our Computer Science Department.  I looked briefly from side to side and noted that there was not a computer on this man’s desk.  

I now looked at him again and noted that I’d seen him before: It was when one of our history faculty had given a presentation on our university in the 1960’s.  

That was weird.

“Ah,” I said, “so are you going to move to your new office now that your papers are graded?”

“Well,” he said with a sad expression. “One of the things about the place I am now is that the papers are never graded, the temperature is never comfortable, and the students show up outside of office hours.”

As he said this, he became first translucent and then transparent and then he was gone.  The papers he was holding dropped to the floor and scatter.  I leaned over to pick one up, and instead of smelling like ditto-fluid, it smelled like dust.

I turned on my heal and beat a hasty retreat.  As I went down the hall, I passed a room that had an old skeleton from biology class stored in it.

It waved at me.

Happy Halloween.