The bounds of min-max pair heap construction

R. A. Chowdhury; M. Z. Rahman; M. Kaykobad

doi:10.1016/S0898-1221(01)00331-5

The bounds of min-max pair heap construction

R. A. Chowdhury
, M. Z. Rahman
, M. Kaykobad

Computer Science

Bangladesh University of Engineering and Technology

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, lower and upper bounds for min-max pair heap construction has been presented. It has been shown that the construction of a min-max pair heap with n elements requires at least 2.07n element comparisons. A new algorithm for creating min-max pair heap has been devised that lowers the upper bound to 2.43n.

Original language	English
Pages (from-to)	911-916
Number of pages	6
Journal	Computers and Mathematics with Applications
Volume	43
Issue number	6-7
DOIs	https://doi.org/10.1016/S0898-1221(01)00331-5
State	Published - Mar 2002

Keywords

Algorithm
Double-ended priority queue
Heap
Min-max heap
Min-max pair heap

Access to Document

10.1016/S0898-1221(01)00331-5

Cite this

@article{3a5b1231217d44fa8a4d77b99557eb01,

title = "The bounds of min-max pair heap construction",

abstract = "In this paper, lower and upper bounds for min-max pair heap construction has been presented. It has been shown that the construction of a min-max pair heap with n elements requires at least 2.07n element comparisons. A new algorithm for creating min-max pair heap has been devised that lowers the upper bound to 2.43n.",

keywords = "Algorithm, Double-ended priority queue, Heap, Min-max heap, Min-max pair heap",

author = "Chowdhury, \{R. A.\} and Rahman, \{M. Z.\} and M. Kaykobad",

year = "2002",

month = mar,

doi = "10.1016/S0898-1221(01)00331-5",

language = "English",

volume = "43",

pages = "911--916",

journal = "Computers and Mathematics with Applications",

issn = "0898-1221",

number = "6-7",

}

TY - JOUR

T1 - The bounds of min-max pair heap construction

AU - Chowdhury, R. A.

AU - Rahman, M. Z.

AU - Kaykobad, M.

PY - 2002/3

Y1 - 2002/3

N2 - In this paper, lower and upper bounds for min-max pair heap construction has been presented. It has been shown that the construction of a min-max pair heap with n elements requires at least 2.07n element comparisons. A new algorithm for creating min-max pair heap has been devised that lowers the upper bound to 2.43n.

AB - In this paper, lower and upper bounds for min-max pair heap construction has been presented. It has been shown that the construction of a min-max pair heap with n elements requires at least 2.07n element comparisons. A new algorithm for creating min-max pair heap has been devised that lowers the upper bound to 2.43n.

KW - Algorithm

KW - Double-ended priority queue

KW - Heap

KW - Min-max heap

KW - Min-max pair heap

UR - https://www.scopus.com/pages/publications/0036498847

U2 - 10.1016/S0898-1221(01)00331-5

DO - 10.1016/S0898-1221(01)00331-5

M3 - Article

AN - SCOPUS:0036498847

SN - 0898-1221

VL - 43

SP - 911

EP - 916

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

IS - 6-7

ER -

The bounds of min-max pair heap construction

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this