ഹീപ് (ഡാറ്റാ സ്ട്രക്‌ച്ചർ)
ട്രീ അടിസ്ഥാനമാക്കി നിർമ്മിക്കുന്ന അരേഖീയമായ ഒരു ഡാറ്റാ സ്ട്രക്‌ച്ചറാണ്‌ ഹീപ്. ഇതിലെ അംഗങ്ങളെല്ലാം താഴെപ്പറയുന്ന നിയമം അനുസരിക്കേണ്ടതാണ്:
- A ഒരു ശീർഷവും B അതിന്റെ പുത്രശീർഷവുമാണെങ്കിൽ A യുടെ കീ B യുടേതിനെക്കാൾ വലുതായിരിക്കണം
അതിനാൽ ഏറ്റവും ഉയർന്ന കീ ഉള്ള അംഗം റൂട്ടിൽ ആയിരിക്കും സ്ഥിതിചെയ്യുന്നത്. ഇത്തരം ഹീപ്പുകളെ മാക്സ്-ഹീപ്പുകൾ എന്നു വിളിക്കുന്നു. ഇതിനു സമാനമായി, ഓരോ ശീർഷത്തിന്റെയും കീ അതിന്റെ പുത്രശീർഷങ്ങളുടെതിനെക്കാൾ ചെറുതാണ്‌ എന്നുണ്ടെങ്കിൽ ഏറ്റവും ചെറിയ കീ ഉള്ള അംഗം റൂട്ടിൽ ആകുകയും ഇത്തരം ഹീപ്പുകൾ മിൻ-ഹീപ്പുകൾ എന്നറിയപ്പെടുകയും ചെയ്യുന്നു.
ഹീപ്പിൽ സാധാരണയായി നടത്തുന്ന പ്രക്രിയകൾ ഇവയാണ്‌:
- ഹീപ്പിലെ റൂട്ട് ശീർഷത്തെ നീക്കം ചെയ്യുക
- മാക്സ്-ഹീപ്പിൽ ഒരു ശീർഷത്തിന്റെ കീ വർദ്ധിപ്പിക്കുക (അഥവാ മിൻ-ഹീപ്പിലാണെങ്കിൽ കുറയ്ക്കുക)
- പുതിയ ഒരംഗത്തെ ഹീപ്പിലേക്ക് ചേർക്കുക
- രണ്ട് ഹീപ്പുകൾ ചേർത്ത് പുതിയൊരു ഹീപ് ഉണ്ടാക്കുക
തരങ്ങൾ
തിരുത്തുകസാധാരണ ഉപയോഗിക്കുന്ന തരം ഹീപ്പുകൾ ബൈനറി ഹീപ്പുകളാണ്‌. ഇവ താഴെപ്പറയുന്ന നിയമങ്ങൾ പാലിച്ചിരിക്കണം :
- ഓരോ ശീർഷത്തിനും രണ്ടോ അതിൽ താഴെയോ പുത്രശീർഷങ്ങൾ മാത്രമേ ഉണ്ടാകാൻ പാടുള്ളൂ
- ഒരു നിശ്ചിത ആഴത്തിൽ ശീർഷങ്ങൾ നിറച്ചതിന്‌ ശേഷമേ അതിന്റെ താഴെയുള്ള ആഴങ്ങളിൽ ശീർഷങ്ങൾ ചേർക്കാൻ പാടുള്ളൂ
- ഏറ്റവും താഴെയുള്ള ആഴത്തിൽ ഇടത്തുനിന്ന് വലത്തോട്ടാണ്‌ പുതിയ ശീർഷങ്ങളെ ചേർക്കേണ്ടത്
ഇവ പൂർണ്ണ ബൈനറി ഹീപ്പുകൾ എന്നും അറിയപ്പെടുന്നു. സാധാരണ ഹീപ് അൽഗൊരിതങ്ങളെല്ലാം ബൈനറി ഹീപ്പുകൾ ഉപയോഗിച്ച് ചെയ്യാൻ സാധിക്കും. മറ്റ് ഹീപ്പുകൾ :
ഉപയോഗങ്ങൾ
തിരുത്തുകവളരെയധികം അൽഗൊരിതങ്ങളിൽ ഉപയോഗിക്കപ്പെടുന്ന ഒരു ഡാറ്റാ സ്ട്രക്‌ച്ചറാണ്‌ ഹീപ്.
- ശരാശരി, മോശം സമയസങ്കീർണ്ണതകൾ ആയുള്ള സോർട്ടിങ്ങ് അൽഗൊരിതമായ ഹീപ് സോർട്ട് ഹീപ് ഉപയോഗിക്കുന്നു. ഇത് ഒരു in-place അൽഗൊരിതം കൂടിയാണ്‌
- ഒരു ലിസ്റ്റിലെ k-ആമത്തെ ഏറ്റവും വലിയ സംഖ്യ ചെറിയ സമയസങ്കീർണ്ണതയോടെ ചെയ്യാൻ ഹീപ് ഉപയോഗിക്കാം
- പ്രിമിന്റെ അൽഗൊരിതം, ഡയക്സ്ട്രയുടെ അൽഗൊരിതം മുതലായ ഗ്രാഫ് അൽഗൊരിതങ്ങൾ സമയസങ്കീർണ്ണത കുറയ്ക്കാൻ ഹീപ് ഉപയോഗിക്കുന്നു.
ഒരു പൂർണ്ണ ബൈനറി ഹീപ് അറേ മാത്രമുപയോഗിച്ച് എളുപ്പത്തിൽ നിർമ്മിക്കാം എന്നതും സമയം കൊണ്ട് N സംഖ്യകളെ ഹീപ്പാക്കി മാറ്റാം എന്നതും ഹീപ്പുകളുടെ പ്രാധാന്യം വർദ്ധിപ്പിക്കുന്നു.
ഇതും കൂടി കാണുക
തിരുത്തുകപുറം കണ്ണികൾ
തിരുത്തുക
- Heap at Wolfram MathWorld
- Explanation of how the basic heap algorithms work