ฮีป (อังกฤษ: Heap) เป็นโครงสร้างข้อมูลที่นำมาสร้างแถวคอยลำดับความสำคัญ (priority queue) รูปแบบหนึ่ง ซึ่งนิยมใช้กันมาก โดยฮีปที่สร้างขึ้นโดยอาศัยแนวคิดจากต้นไม้ทวิภาคใช้ชื่อว่า "ฮีปทวิภาค" (binary heap) ซึ่งยังมีการสร้างฮีปโดยอาศัยแนวคิดแบบอื่น ๆ ได้อีกเช่น ฟีโบนักชีฮีป (fibonacci heap) โดยฮีปทุกชนิดนั้นมีความสัมพันธ์เหมือนกันคือปมพ่อมีลำดับความสำคัญมากกว่าปมลูก
| ฮีป |
|---|
รูปแบบการเรียงตัวของฮีปทวิภาค (binary heap) โดยสมาชิกที่สำคัญกว่า (ในที่นี้เป็นฮีปมากสุดคือเลขที่มีค่ามากจะสำคัญ) จะอยู่ด้านบน |
| ความสำคัญของลำดับ | FIFO (First In First Out) แต่เรียงตามลำดับความสำคัญ |
|---|
| การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำกันได้ |
|---|
| เวลาที่ใช้ในการเข้าถึง | O(log n) |
|---|
| การทำให้ว่าง | ทำให้ทุกตัวเป็น null |
|---|
| เวลาที่ใช้ทำให้ว่าง | O(n) |
|---|
| ความซับซ้อนในการคำนวณแบบสัญกรณ์โอใหญ่ |
|---|
| ขั้นตอนวิธี | | ถัวเฉลี่ย | เลวร้ายที่สุด |
|---|
|
แนวคิดของฮีปนอกจากนำมาสร้างแถวคอยลำดับความสำคัญแล้ว ยังนำมาประยุกต์ใช้ในการสร้างโครงสร้างข้อมูลอื่นๆ เช่นทรีพ เป็นต้น
ฮีปเป็นต้นไม้ประเภทหนึ่งซึ่งจะจัดความสัมพันธ์ให้ปมพ่อ มีความสำคัญ(priority)มากกว่าปมลูก
ฮีปรูปแบบต่างๆ - ฮีปเติมเต็ม (completed heap) นอกจากที่จะเป็นฮีปแล้ว ยังเป็นต้นไม้เติมเต็ม(comleted tree)อีกด้วย ซึ่งฮีปประเภทนี้จะสามารถสร้างได้ด้วยแถวลำดับ
- ฮีปน้อยสุด (least heap) เป็นฮีปที่แทนความสำคัญด้วยตัวเลข โดยตัวเลขยิ่งน้อยจะยิ่งมีความสำคัญมาก เมื่อเขียนในรูปต้นไม้จะเหมือนว่าปมพ่อจะมีเลขความสำคัญน้อยกว่าปมลูกเสมอ
- ฮีปมากสุด (most heap) เป็นฮีปที่แทนความสำคัญด้วยตัวเลข โดยตัวเลขยิ่งมากจะยิ่งมีความสำคัญมาก เมื่อเขียนในรูปต้นไม้จะเหมือนว่าปมพ่อจะมีเลขความสำคัญมากกว่าปมลูก
- ทรีพ (treap) เป็นโครงสร้างข้อมูลที่สร้างข้อมูลเสริมให้มีความสัมพันธ์แบบฮีป ส่วนข้อมูลหลักจะเรียงความสัมพันธ์แบบต้นไม้ค้นหาแบบทวิภาค
จุดเด่นของฮีป ฮีปมีจุดเด่นในการเรียงลำดับในลักษณะต้นไม้ โดยเมื่อเรียงแล้วสมาชิกที่มีความสำคัญสูงสุดจะอยู่สูงสุดหรือเป็นราก ทำให้เข้าถึงข้อมูลที่มีความสำคัญสูงได้ง่าย อีกทั้งการเรียงแบบต้นไม้ โดยเฉพาะฮีปเติมเต็มด้วยแล้ว จึงสามารถลดเวลาการเข้าถึงลงเป็น O(log n)
บริการที่มักจะมี บริการนั้นจะเน้นบริการเดียวกับแถวคอยลำดับความสำคัญ
- เพิ่มรายการแนบด้วยระดับไว้ในแถวคอย (enqueue)
- ลบรายการที่มีความสำคัญสูงสุดและคืนค่านั้นกลับมา (prioritized dequeue)
- ดึงค่ารายการที่มีความสำคัญสูงสุดโดยไม่ลบรายการนั้นออก (peek)
ความเร็วที่ใช้ในการทำงาน จากการที่ฮีปเรียงตัวในลักษณะต้นไม้ โดยเฉพาะฮีปเติมเต็ม ทำให้ต้นไม้ที่ได้เป็นต้นไม้ประกันความสูง จึงเป็นการประกันการทำงานว่าอย่างมากจะใช้เวลา O(log n) และเข้าถึงข้อมูลที่สำคัญที่สุดได้ง่ายเพราะอยู่บนรากเป็นเวลาคงที่ O(1)
ประเภทข้อมูลที่ใช้สร้างฮีป เนื่องจากฮีปเป็นต้นไม้จึงอาจสร้างในลักษณะปมของต้นไม้ได้ ซึ่งใช้ประเภทข้อมูลประเภทโครงสร้าง หรือวัตถุ อย่างไรก็ตาม โดยปกติสำหรับการสร้างแถวคอยลำดับความสำคัญเราจะสร้างแบบฮีปเติมเต็ม ซึ่งสามารถใช้ความสัมพันธ์ทางคณิตศาสตร์ ทำให้เราสามารถใช้แถวลำดับในการสร้างฮีปเติมเต็มได้
ความสัมพันธ์ระหว่างดัชนีของปมพ่อและปมลูกในแถวลำดับของฮีปเติมเต็ม
เมื่อเราแวะผ่านฮีปเติมเต็มตามความกว้าง(bread-first search)และเรียงเป็นแถวลำดับแล้ว เราจะได้ความสำคัญที่ว่าสำหรับสมาชิกดัชนีที่ i ใดๆ
- ปมพ่อของสมาชิกตัวนี้อยู่ที่
- ปมลูกทั้งสองตัวของสมาชิกตัวนี้อยู่ที่
การสร้างบริการของฮีป ในที่นี้กล่าวถึงลักษณะการทำงานของฮีปเติมเต็มในการทำแถวคอยลำดับความสำคัญ สำหรับการทำงานของทรีพให้ดูทรีพ#การสร้างบริการของทรีพ
การเข้าแถวคอย
ทำได้โดยการเพิ่มสมาชิกไปที่หลังสุดของแถวลำดับก่อน และทำการสลับข้อมูลกับปมพ่อ(percolate up)เมื่อข้อมูลใหม่มีลำดับความสำคัญมากกว่า จนกระทั่งปมพ่อมีลำดับความสำคัญมากกว่าจึงหยุด
การลบสมาชิกที่สำคัญที่สุด
ทำได้โดยการดึงเอาข้อมูลแรกสุดของแถวลำดับ กล่าวคือเป็นรากของฮีปเติมเต็ม ซึ่งจะมีลำดับความสำคัญมากที่สุดออก จากนั้นจะหยิบตัวสุดท้ายของแถวลำดับมาแทน (ซึ่งมักจะมีลำดับความสำคัญน้อย)และทำการลดลำดับลงโดยการสลับข้อมูลกับปมลูก(percolate down)จนข้อมูลสลับจนปมลูกมีลำดับความสำคัญน้อยกว่าจึงหยุด
ดูเพิ่ม โครงสร, างข, อม, งก, ามภาษา, ในบทความน, ไว, ให, านและผ, วมแก, ไขบทความศ, กษาเพ, มเต, มโดยสะดวก, เน, องจากว, เด, ยภาษาไทยย, งไม, บทความด, งกล, าว, กระน, ควรร, บสร, างเป, นบทความโดยเร, วท, ดฮ, งกฤษ, heap, เป, นโครงสร, างข, อม, ลท, นำมาสร, างแถวคอยลำด, บความสำค, . lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisudhip xngkvs Heap epnokhrngsrangkhxmulthinamasrangaethwkhxyladbkhwamsakhy priority queue rupaebbhnung sungniymichknmak odyhipthisrangkhunodyxasyaenwkhidcaktnimthwiphakhichchuxwa hipthwiphakh binary heap sungyngmikarsranghipodyxasyaenwkhidaebbxun idxikechn fiobnkchihip fibonacci heap odyhipthukchnidnnmikhwamsmphnthehmuxnknkhuxpmphxmiladbkhwamsakhymakkwapmlukhiprupaebbkareriyngtwkhxnghipthwiphakh binary heap odysmachikthisakhykwa inthiniepnhipmaksudkhuxelkhthimikhamakcasakhy caxyudanbnkhwamsakhykhxngladbFIFO First In First Out aeteriyngtamladbkhwamsakhykarsaknkhxngsmachikxnuyatihsaknidewlathiichinkarekhathungO log n karthaihwangthaihthuktwepn nullewlathiichthaihwangO n khwamsbsxninkarkhanwnaebbsykrnoxihykhntxnwithithwechliyelwraythisudaenwkhidkhxnghipnxkcaknamasrangaethwkhxyladbkhwamsakhyaelw yngnamaprayuktichinkarsrangokhrngsrangkhxmulxun echnthriph epntn enuxha 1 lksnakhxnghip 2 hiprupaebbtang 3 cudednkhxnghip 4 brikarthimkcami 5 khwamerwthiichinkarthangan 6 praephthkhxmulthiichsranghip 6 1 khwamsmphnthrahwangdchnikhxngpmphxaelapmlukinaethwladbkhxnghipetimetm 7 karsrangbrikarkhxnghip 7 1 karekhaaethwkhxy 7 2 karlbsmachikthisakhythisud 8 duephimlksnakhxnghip aekikhhipepntnimpraephthhnungsungcacdkhwamsmphnthihpmphx mikhwamsakhy priority makkwapmlukhiprupaebbtang aekikhhipetimetm completed heap nxkcakthicaepnhipaelw yngepntnimetimetm comleted tree xikdwy sunghippraephthnicasamarthsrangiddwyaethwladb hipnxysud least heap epnhipthiaethnkhwamsakhydwytwelkh odytwelkhyingnxycayingmikhwamsakhymak emuxekhiyninruptnimcaehmuxnwapmphxcamielkhkhwamsakhynxykwapmlukesmx hipmaksud most heap epnhipthiaethnkhwamsakhydwytwelkh odytwelkhyingmakcayingmikhwamsakhymak emuxekhiyninruptnimcaehmuxnwapmphxcamielkhkhwamsakhymakkwapmluk thriph treap epnokhrngsrangkhxmulthisrangkhxmulesrimihmikhwamsmphnthaebbhip swnkhxmulhlkcaeriyngkhwamsmphnthaebbtnimkhnhaaebbthwiphakhcudednkhxnghip aekikhhipmicudedninkareriyngladbinlksnatnim odyemuxeriyngaelwsmachikthimikhwamsakhysungsudcaxyusungsudhruxepnrak thaihekhathungkhxmulthimikhwamsakhysungidngay xikthngkareriyngaebbtnim odyechphaahipetimetmdwyaelw cungsamarthldewlakarekhathunglngepn O log n brikarthimkcami aekikhbrikarnncaennbrikarediywkbaethwkhxyladbkhwamsakhy ephimraykaraenbdwyradbiwinaethwkhxy enqueue lbraykarthimikhwamsakhysungsudaelakhunkhannklbma prioritized dequeue dungkharaykarthimikhwamsakhysungsudodyimlbraykarnnxxk peek khwamerwthiichinkarthangan aekikhcakkarthihiperiyngtwinlksnatnim odyechphaahipetimetm thaihtnimthiidepntnimpraknkhwamsung cungepnkarpraknkarthanganwaxyangmakcaichewla O log n aelaekhathungkhxmulthisakhythisudidngayephraaxyubnrakepnewlakhngthi O 1 praephthkhxmulthiichsranghip aekikhenuxngcakhipepntnimcungxacsranginlksnapmkhxngtnimid sungichpraephthkhxmulpraephthokhrngsrang hruxwtthu xyangirktam odypktisahrbkarsrangaethwkhxyladbkhwamsakhyeracasrangaebbhipetimetm sungsamarthichkhwamsmphnththangkhnitsastr thaiherasamarthichaethwladbinkarsranghipetimetmid khwamsmphnthrahwangdchnikhxngpmphxaelapmlukinaethwladbkhxnghipetimetm aekikh emuxeraaewaphanhipetimetmtamkhwamkwang bread first search aelaeriyngepnaethwladbaelw eracaidkhwamsakhythiwasahrbsmachikdchnithi i id pmphxkhxngsmachiktwnixyuthi i 1 2 displaystyle Big lfloor frac i 1 2 Big rfloor pmlukthngsxngtwkhxngsmachiktwnixyuthi 2 i 1 2 i 2 displaystyle 2i 1 2i 2 karsrangbrikarkhxnghip aekikhinthiniklawthunglksnakarthangankhxnghipetimetminkarthaaethwkhxyladbkhwamsakhy sahrbkarthangankhxngthriphihduthriph karsrangbrikarkhxngthriph karekhaaethwkhxy aekikh thaidodykarephimsmachikipthihlngsudkhxngaethwladbkxn aelathakarslbkhxmulkbpmphx percolate up emuxkhxmulihmmiladbkhwamsakhymakkwa cnkrathngpmphxmiladbkhwamsakhymakkwacunghyud karlbsmachikthisakhythisud aekikh thaidodykardungexakhxmulaerksudkhxngaethwladb klawkhuxepnrakkhxnghipetimetm sungcamiladbkhwamsakhymakthisudxxk caknncahyibtwsudthaykhxngaethwladbmaaethn sungmkcamiladbkhwamsakhynxy aelathakarldladblngodykarslbkhxmulkbpmluk percolate down cnkhxmulslbcnpmlukmiladbkhwamsakhynxykwacunghyudduephim aekikhaethwkhxyladbkhwamsakhy thriphekhathungcak https th wikipedia org w index php title hip okhrngsrangkhxmul amp oldid 9355450, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
