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

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

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

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

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

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

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

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

 ഉപയോഗങ്ങൾ 
വളരെയധികം അൽഗൊരിതങ്ങളിൽ ഉപയോഗിക്കപ്പെടുന്ന ഒരു ഡാറ്റാ സ്ട്രക്‌ച്ചറാണ്‌ ഹീപ്.
 ശരാശരി, മോശം സമയസങ്കീർണ്ണതകൾ  ആയുള്ള സോർട്ടിങ്ങ് അൽഗൊരിതമായ ഹീപ് സോർട്ട് ഹീപ് ഉപയോഗിക്കുന്നു. ഇത് ഒരു in-place അൽഗൊരിതം കൂടിയാണ്‌
 ഒരു ലിസ്റ്റിലെ k-ആമത്തെ ഏറ്റവും വലിയ സംഖ്യ ചെറിയ സമയസങ്കീർണ്ണതയോടെ ചെയ്യാൻ ഹീപ് ഉപയോഗിക്കാം
 പ്രിമിന്റെ അൽഗൊരിതം, ഡയക്സ്ട്രയുടെ അൽഗൊരിതം മുതലായ ഗ്രാഫ് അൽഗൊരിതങ്ങൾ സമയസങ്കീർണ്ണത കുറയ്ക്കാൻ ഹീപ് ഉപയോഗിക്കുന്നു.

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

 ഇതും കൂടി കാണുക 
 ഹീപ് സോർട്ട്

പുറം കണ്ണികൾ

Heap at Wolfram MathWorld
Explanation of how the basic heap algorithms work

വർഗ്ഗം:ഡാറ്റാ സ്ട്രക്‌ച്ചറുകൾ