Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ในวิทยาการคอมพิวเตอร์ โดย Soft heap เป็นตัวแปรในโครงสร้างข้อมูล(Data structure) heap ง่ายๆ ซึ่งมีคำสั่งที่สามารถสั่งงานได้ 5 ชนิด นี่คือการลุล่วงคำสั่งโดยการ " corrupting(ทำความเสียหาย)" (การเพิ่มขึ้น) เป็นกุญแจสำคัญในค่าของจำนวนที่แน่นอนที่อยู่ใน Heap โดยมีคำสั่งที่ให้ในการดำเนินการดังนี้
- create(S): สร้างsoft heap(S) ขึ้นมาใหม่
- insert(S, x): แทรกสมาชิก (x) ใน soft heap (S)
- meld(S, S’): รวม 2 รายการที่อยู่ใน soft heaps เป็นอันเดียว(สร้างSoft Heap ใหม่)และทำลายทั้งสองทิ้ง(อันเก่า)
- delete(S, x): ลบสมาชิก(x)จาก soft heap (S)
- findmin(S): เรียกคืนค่า(return)สมาชิกใน Soft Heap (S) กับค่าKeysที่เล็กที่สุด
Heapอื่น ๆ เช่น heaps Fibonacci สามารถทำคำสั่งได้สำเร็จมากที่สุดโดยไม่มีจำเป็นต้องมี"corrupting", แต่ไม่สามารถให้ขอบเขตเวลาคงที่บนการดำเนินการในคำสั่ง “ลบ” (delete) ที่สำคัญได้ ปริมาณของ Corruptionสามารถควบคุมได้โดยการเลือกพารามิเตอร์ “ε”, แต่การตั้งค่าต่ำกว่านี้จำเป็นต้องมีการใส่เวลามากขึ้นด้วยเช่นกัน (O(log 1/ε) สำหรับอัตราการผิดพลาดของ ε)
ท้ายที่สุดอัลกรอลิทึมจะมีลักษณะดังนี้:
function softHeapSelect(a[1..n], k) if k = 1 then return minimum(a[1..n]) create(S) for i from 1 to n insert(S, a[i]) for i from 1 to n/3 x := findmin(S) delete(S, x) xIndex := partition(a, x) // Returns new index of pivot x if k < xIndex softHeapSelect(a[1..xIndex-1], k) else softHeapSelect(a[xIndex..n], k-xIndex+1)
ค่าตัวแปรทั่วไปที่ใช้ในการเรียงลำดับความสำคัญ เรียกว่า “Soft Heap” โครงสร้างข้อมูลจะถูกสนับสนุนโดยกระบวนการหลักดังนี้ : insert(การแทรก), delete(การลบ), meld(การรวม), findmin(หาค่าที่น้อยที่สุด) เป็นที่น่าแปลกใจมากที่มันมีความสามารถในการเอาชนะขอบเขตของลอกาลึทึมบนความซับซ้อนของ Heap ในแบบจำลองการเปรียบเทียบพื้นฐาน เพื่อที่ทำลายอุปสรรค์ของทฤษฎีนี้ เอนโทรปีของโครงสร้างข้อมูลจะถูกทำให้ลดลงโดยค่าบางค่าในKeys ซึ่งมีการผสมลำดับของ n คำสั่งกับค่าของความผิดพลาด(Error rate, ε) จะมีค่าอยู่ระหว่าง (0< ε ≤ 1/2) สิ่งที่เป็นข้อยืนยันคือในเวลาใดๆ ส่วนมาก ε*n มันจะมี keys จะถูกยกขึ้นมาใช้งาน ,การหักล้างความซับซ้อนของแต่ละคำสั่งนั้นเป็นที่แน่นอน ยกเว้นในคำสั่ง Insert ซึ่งจะใช้เวลา O(Log 1/ε) ครั้ง
Soft Heap จะดีที่สุดก็ต่อเมื่อมีค่าของ ε อยู่ในแบบจำลองการเปรียบเทียบพื้นฐาน โดยโครงสร้างข้อมูลนั้นจะมีแค่Pointer อยู่อย่างเดียว ไม่มี Array ใดๆที่จะใช้ค่าเลขสมมุติในการสร้าง Keys ได้ แนวความคิดหลักของ Soft Heap คือการเคลื่อนย้ายรายการข้ามโครงสร้างข้อมูลไม่ใช่ทีละรายการแต่เป็นกลุ่ม นั้นเป็นไปอย่างปกติ, ในโครงสร้างข้อมูลจะมีลักษณะคล้ายกับ Carpooling (การร่วมโดยสารกันไปในเส้นทางเดียวกัน โดยในยานพาหนะเดียวกัน) Keys จะต้องขึ้นอยู่กับผลของมัน เพื่อที่จะรักษาลำดับโครงสร้างข้อมูลของ Heap เอาไว้ Soft Heap สามารถใช้การคำนวณได้อย่างแน่นอนหรือ มีค่ามัธฐาน และค่าเปอร์เซ็นสูงสุด มันมีประโยชน์มากสำหรับการประมาณค่าการเรียงลำดับข้อมูล(Sorting)และ เพื่อคำนวณหาค่าที่ต่ำที่สุดของแผนภูมิต้นไม้อีกด้วย
อ้างอิง
- Chazelle, Bernard (November 2000). "The soft heap: an approximate priority queue with optimal error rate" (PDF). J. ACM. 47 (6): 1012–1027. CiteSeerX10.1.1.5.9705 . doi:10.1145/355541.355554
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
inwithyakarkhxmphiwetxr ody Soft heap epntwaeprinokhrngsrangkhxmul Data structure heap ngay sungmikhasngthisamarthsngnganid 5 chnid nikhuxkarlulwngkhasngodykar corrupting thakhwamesiyhay karephimkhun epnkuyaecsakhyinkhakhxngcanwnthiaennxnthixyuin Heap odymikhasngthiihinkardaeninkardngni create S srangsoft heap S khunmaihm insert S x aethrksmachik x in soft heap S meld S S rwm 2 raykarthixyuin soft heaps epnxnediyw srangSoft Heap ihm aelathalaythngsxngthing xneka delete S x lbsmachik x cak soft heap S findmin S eriykkhunkha return smachikin Soft Heap S kbkhaKeysthielkthisud Heapxun echn heaps Fibonacci samarththakhasngidsaercmakthisudodyimmicaepntxngmi corrupting aetimsamarthihkhxbekhtewlakhngthibnkardaeninkarinkhasng lb delete thisakhyid primankhxng Corruptionsamarthkhwbkhumidodykareluxkpharamietxr e aetkartngkhatakwanicaepntxngmikarisewlamakkhundwyechnkn O log 1 e sahrbxtrakarphidphladkhxng e thaythisudxlkrxlithumcamilksnadngni function softHeapSelect a 1 n k if k 1 then return minimum a 1 n create S for i from 1 to n insert S a i for i from 1 to n 3 x findmin S delete S x xIndex partition a x Returns new index of pivot x if k lt xIndex softHeapSelect a 1 xIndex 1 k else softHeapSelect a xIndex n k xIndex 1 khatwaeprthwipthiichinkareriyngladbkhwamsakhy eriykwa Soft Heap okhrngsrangkhxmulcathuksnbsnunodykrabwnkarhlkdngni insert karaethrk delete karlb meld karrwm findmin hakhathinxythisud epnthinaaeplkicmakthimnmikhwamsamarthinkarexachnakhxbekhtkhxnglxkaluthumbnkhwamsbsxnkhxng Heap inaebbcalxngkarepriybethiybphunthan ephuxthithalayxupsrrkhkhxngthvsdini exnothrpikhxngokhrngsrangkhxmulcathukthaihldlngodykhabangkhainKeys sungmikarphsmladbkhxng n khasngkbkhakhxngkhwamphidphlad Error rate e camikhaxyurahwang 0 lt e 1 2 singthiepnkhxyunynkhuxinewlaid swnmak e n mncami keys cathukykkhunmaichngan karhklangkhwamsbsxnkhxngaetlakhasngnnepnthiaennxn ykewninkhasng Insert sungcaichewla O Log 1 e khrng Soft Heap cadithisudktxemuxmikhakhxng e xyuinaebbcalxngkarepriybethiybphunthan odyokhrngsrangkhxmulnncamiaekhPointer xyuxyangediyw immi Array idthicaichkhaelkhsmmutiinkarsrang Keys id aenwkhwamkhidhlkkhxng Soft Heap khuxkarekhluxnyayraykarkhamokhrngsrangkhxmulimichthilaraykaraetepnklum nnepnipxyangpkti inokhrngsrangkhxmulcamilksnakhlaykb Carpooling karrwmodysarknipinesnthangediywkn odyinyanphahnaediywkn Keys catxngkhunxyukbphlkhxngmn ephuxthicarksaladbokhrngsrangkhxmulkhxng Heap exaiw Soft Heap samarthichkarkhanwnidxyangaennxnhrux mikhamththan aelakhaepxresnsungsud mnmipraoychnmaksahrbkarpramankhakareriyngladbkhxmul Sorting aela ephuxkhanwnhakhathitathisudkhxngaephnphumitnimxikdwyxangxingChazelle Bernard November 2000 The soft heap an approximate priority queue with optimal error rate PDF J ACM 47 6 1012 1027 CiteSeerX10 1 1 5 9705 doi 10 1145 355541 355554