Jump to content

ഹീപ് (ഡാറ്റാ സ്ട്രക്‌ച്ചർ)

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
ഒരു പൂർണ്ണ ബൈനറി മാക്സ്-ഹീപ്

ട്രീ അടിസ്ഥാനമാക്കി നിർമ്മിക്കുന്ന അരേഖീയമായ ഒരു ഡാറ്റാ സ്ട്രക്‌ച്ചറാണ്‌ ഹീപ്. ഇതിലെ അംഗങ്ങളെല്ലാം താഴെപ്പറയുന്ന നിയമം അനുസരിക്കേണ്ടതാണ്:

  • A ഒരു ശീർഷവും B അതിന്റെ പുത്രശീർഷവുമാണെങ്കിൽ A യുടെ കീ B യുടേതിനെക്കാൾ വലുതായിരിക്കണം

അതിനാൽ ഏറ്റവും ഉയർന്ന കീ ഉള്ള അംഗം റൂട്ടിൽ ആയിരിക്കും സ്ഥിതിചെയ്യുന്നത്. ഇത്തരം ഹീപ്പുകളെ മാക്സ്-ഹീപ്പുകൾ എന്നു വിളിക്കുന്നു. ഇതിനു സമാനമായി, ഓരോ ശീർഷത്തിന്റെയും കീ അതിന്റെ പുത്രശീർഷങ്ങളുടെതിനെക്കാൾ ചെറുതാണ്‌ എന്നുണ്ടെങ്കിൽ ഏറ്റവും ചെറിയ കീ ഉള്ള അംഗം റൂട്ടിൽ ആകുകയും ഇത്തരം ഹീപ്പുകൾ മിൻ-ഹീപ്പുകൾ എന്നറിയപ്പെടുകയും ചെയ്യുന്നു.

ഹീപ്പിൽ സാധാരണയായി നടത്തുന്ന പ്രക്രിയകൾ ഇവയാണ്‌:

  • ഹീപ്പിലെ റൂട്ട് ശീർഷത്തെ നീക്കം ചെയ്യുക
  • മാക്സ്-ഹീപ്പിൽ ഒരു ശീർഷത്തിന്റെ കീ വർദ്ധിപ്പിക്കുക (അഥവാ മിൻ-ഹീപ്പിലാണെങ്കിൽ കുറയ്ക്കുക)
  • പുതിയ ഒരംഗത്തെ ഹീപ്പിലേക്ക് ചേർക്കുക
  • രണ്ട് ഹീപ്പുകൾ ചേർത്ത് പുതിയൊരു ഹീപ് ഉണ്ടാക്കുക

തരങ്ങൾ

[തിരുത്തുക]

സാധാരണ ഉപയോഗിക്കുന്ന തരം ഹീപ്പുകൾ ബൈനറി ഹീപ്പുകളാണ്‌. ഇവ താഴെപ്പറയുന്ന നിയമങ്ങൾ പാലിച്ചിരിക്കണം :

  • ഓരോ ശീർഷത്തിനും രണ്ടോ അതിൽ താഴെയോ പുത്രശീർഷങ്ങൾ മാത്രമേ ഉണ്ടാകാൻ പാടുള്ളൂ
  • ഒരു നിശ്ചിത ആഴത്തിൽ ശീർഷങ്ങൾ നിറച്ചതിന്‌ ശേഷമേ അതിന്റെ താഴെയുള്ള ആഴങ്ങളിൽ ശീർഷങ്ങൾ ചേർക്കാൻ പാടുള്ളൂ
  • ഏറ്റവും താഴെയുള്ള ആഴത്തിൽ ഇടത്തുനിന്ന് വലത്തോട്ടാണ്‌ പുതിയ ശീർഷങ്ങളെ ചേർക്കേണ്ടത്

ഇവ പൂർണ്ണ ബൈനറി ഹീപ്പുകൾ എന്നും അറിയപ്പെടുന്നു. സാധാരണ ഹീപ് അൽഗൊരിതങ്ങളെല്ലാം ബൈനറി ഹീപ്പുകൾ ഉപയോഗിച്ച് ചെയ്യാൻ സാധിക്കും. മറ്റ് ഹീപ്പുകൾ :

ഉപയോഗങ്ങൾ

[തിരുത്തുക]

വളരെയധികം അൽഗൊരിതങ്ങളിൽ ഉപയോഗിക്കപ്പെടുന്ന ഒരു ഡാറ്റാ സ്ട്രക്‌ച്ചറാണ്‌ ഹീപ്.

ഒരു പൂർണ്ണ ബൈനറി ഹീപ് അറേ മാത്രമുപയോഗിച്ച് എളുപ്പത്തിൽ നിർമ്മിക്കാം എന്നതും സമയം കൊണ്ട് N സംഖ്യകളെ ഹീപ്പാക്കി മാറ്റാം എന്നതും ഹീപ്പുകളുടെ പ്രാധാന്യം വർദ്ധിപ്പിക്കുന്നു.

ഇതും കൂടി കാണുക

[തിരുത്തുക]

പുറം കണ്ണികൾ

[തിരുത്തുക]
  • Heap at Wolfram MathWorld
  • Explanation of how the basic heap algorithms work