On the Tree Structure of Some Worst Inputs for Heapsort (<Special Issue>Special Issue on Selected Papers from LA Symposium)

スポンサーリンク

概要

• 論文の詳細を見る

• By a worst input (for the selection phase of Heapsort) of size n, we mean a heap of size n such that, if it is given to the selection phase of Heapsort, the number of movements of data is maximum among the numbers of movements for all heaps of size n. D.E. Knuth showed a special type of worst inputs which we will call the K-type heaps. His definition of K-type heaps was by the induction on the size n. We give one characterization of K-type worst heaps that is based on their tree structure. This characterization gives more information on the tree structure of K-type heaps than the Knuth's definition.

• 一般社団法人電子情報通信学会の論文
• 2003-02-01

著者

• Fukada Yoshie

  Faculty Of Engineering Soka University

• TOMITSURU Yoshitomo

  Faculty of Engineering, Soka University

• KOBAYASHI Kojiro

  Faculty of Engineering, Soka University

• Tomitsuru Yoshitomo

  Faculty Of Engineering Soka University:(present Address)bansei Junior High School

• Kobayashi Kojiro

  Faculty Of Engineering Soka University

関連論文

• On the Tree Structure of Some Worst Inputs for Heapsort (Special Issue on Selected Papers from LA Symposium)
• On Malign Input Distributions for Algorithms

スポンサーリンク