PERFORMANCE APPRAISAL OF TREAP AND HEAP SORT ALGORITHMS

  • A. D. GBADEBO Department of Computer Science, Michael Otedola College of Primary Education, Noforija–Epe, Lagos State, Nigeria
  • A. T. AKINWALE Department of Computer Science, Federal University of Agriculture, Abeokuta, Nigeria
  • S. AKINLEYE Department of Mathematics, Federal University of Agriculture, Abeokuta, Nigeria
Keywords: Algorithm, heap, node, treap, tree

Abstract

The task of storing items to allow for fast access to an item given its key is an ubiquitous problem in many organizations. Treap as a method uses key and priority for searching in databases. When the keys are drawn from a large totally ordered set, the choice of storing the items is usually some sort of search tree. The simplest form of such tree is a binary search tree. In this tree, a set X of n items is stored at the nodes of a rooted binary tree in which some item y ϵ X is chosen to be stored at the root of the tree. Heap as data structure is an array object that can be viewed as a nearly complete binary tree in which each node of the tree corresponds to an element of the array that stores the value in the node. Both algorithms were subjected to sorting under the same experimental environment and conditions. This was implemented by means of threads which call each of the two methods simultaneously. The server keeps records of individual search time which was the basis of the comparison. It was discovered that treap was faster than heap sort in sorting and searching for elements using systems with homogenous properties.

 

 

References

Aragon, C.R. and Seidel, R. 1989. Randomized Search Trees. Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS) Washington, D.C.: IEEE Computer Society Press, pp. 540–545.

Blelloch, G.E. and Reid-Miller, M. 2011. Fast Set Operations Using Treaps. 10th Annual ACM Symposium: Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architectures. New York, USA: ACM, pp. 16–26.

Cormen, H.T., Leiserson, C.E., Rivest, R.L. and Stein, C. 2002. Introduction to Algorithms 2nd Edition. The Massachusetts Institute of Technology. pp. 150-157.

Galperin, I. and Rivest, R.L. 2003. Scapegoat Trees. Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, 165-174.

Melhorn, K. and Naher, S. 2002. Algorithm Design and Software Libraries: Recent Development in the LEDA Project. Algorithms, software, Architectures, Information Processing. Vol. 9.Elsevier Science Publishers.

Mikkel, T. 2008. Faster deterministic sorting and priority queues in linear space. Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. pp. 550–555.

Seidel, R. and Aragon, C.R. 2001. Randomized Strategies for Maintaining Balance in Binary Search Trees. Algorithmica, 23: 218-223.

Seidel, R. and Aragon, C.R. 1996. Randomized Search Trees. Algorithmica, 16(4 &5): 464–497.
Published
2020-10-05
Section
Articles