fbpx
วิกิพีเดีย

แถวคอยลำดับความสำคัญ

แถวคอยลำดับความสำคัญ

ความสำคัญของลำดับ FIFO (First In Fast Out) แต่เรียงตามลำดับความสำคัญ
การซ้ำกันของสมาชิก อนุญาตให้ซ้ำกันได้
วิธีการเข้าถึง(access) ENQUEUE/DEQUEUE (เรียงตามลำดับความสำคัญ)
เวลาที่ใช้ในการเข้าถึง O (1)
โครงสร้างข้อมูลที่มีรูปแบบนี้ ฮีป

ในแถวคอยปกติ ข้อมูลที่เข้ามาก่อนจะมีสิทธิ์ออกก่อน (First In First Out:FIFO) อย่างไรก็ตาม มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่นการให้คิวงานที่เล็กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท เช่นนี้เราจะสร้าง แถวคอยลำดับความสำคัญ (อังกฤษ: Priority Queue) เป็นคิวที่ถึงแม้เข้าก่อน แต่สิ่งที่มีความสำคัญมากกว่าจะได้ออกก่อน ถ้ามีความสำคัญเท่ากัน ข้อมูลที่เข้ามาก่อนจะได้ออกก่อนเช่นเดียวกับแถวคอยปกติ

แถวคอยลำดับความสำคัญทำให้เราสามารถประยุกต์ใช้คิวได้ดีขึ้น เนื่องจากเพิ่มการให้ความสำคัญของสมาชิกที่แตกต่างกัน ส่งผลให้เราสามารถจัดเรียงแถวคอยได้ใหม่ให้เหมาะสมกับการทำงานได้ เราใช้แถวคอยลำดับความสำคัญในการจัดการทำงาน การตรวจนับ ฯลฯ

จุดเด่น

แถวคอยลำดับความสำคัญสามารถดึงตัวที่สำคัญที่สุดลัดแถวออกมาก่อน โดยใช้เวลาคงที่ จึงทำให้จัดการทำงานได้อย่างสอดคล้องกับความเป็นจริงมากยิ่งขึ้น ทำให้สามารถจัดลำดับในการทำงานได้ดี เช่น การจัดการทำงานของเครื่องพิมพ์ที่อนุญาตให้งานเล็กๆได้พิมพ์ก่อน เพื่อจะได้ไม่เสียเวลา

บริการที่มักจะมี

  • เพิ่มรายการแนบด้วยระดับไว้ในแถวคอย (enqueue)
  • ลบรายการที่มีความสำคัญสูงสุดและคืนค่านั้นออกมา (prioritized dequeue)
  • ดึงค่ารายการที่มีความสำคัญสูงสุดโดยไม่ลบรายการนั้นออก (peek)

ตัวอย่างการเขียนโปรแกรม (ภาษา C++)

#include <bits/stdc++.h> using namespace std; class node{ public: int age; string name; node(int a, string b){ age = a; name = b; } }; bool operator<(const node& a, const node& b) { node temp1=a,temp2=b; if(a.age != b.age) return a.age > b.age; else{ return temp1.name.append(temp2.name) > temp2.name.append(temp1.name); } } int main(){ priority_queue<node> pq; node b(23,"Somchai"); node a(22,"Pongsak"); node c(22,"Manee"); pq.push(b); pq.push(a); pq.push(c); int size = pq.size(); for (int i = 0; i < size; ++i) { cout<<pq.top().age<<" "<<pq.top().name<<"\n"; pq.pop(); } } 

จากโปรแกรมข้างต้น เราจะทำการสร้าง แถวคอย โดยโปรแกรมมีเงื่อนไขว่า ใครที่อายุ(Age)น้อยที่สุด จะถูกเรียกชื่อก่อนเสมอ โดยหากมีหลายคนที่อายุเท่ากัน คนที่ถูกเพิ่มเข้าไปในคิวภายหลังจากถูกเรียกก่อนเสมอ

ลำดับการเพิ่มข้อมูล

  1. Somchai อายุ 23 ปี >> node a(23,"Somchai");
  2. Pongsak อายุ 22 ปี >> node b(22,"Pongsak");
  3. Manee อายุ 22 ปี >> node c(22,"Manee");

ผลการทำงานของโปรแกรม

22 Manee

22 Pongsak

23 Somchai

จากผลการทำงานของโปรแกรมข้างต้น จะสังเกตได้ว่า ถึงแม้ Somchai จะมาก่อน แต่ว่าจะถูกเรียกท้ายสุดเพราะอายุมากที่สุด ส่วน Manee จะถูกเรียกเป็นอันดับแรก ถึงแม้ว่าจะอายุเท่ากันกับ Pongsak แต่ว่า Manee มาทีหลังสุด ดังนั้นจึงได้ความสำคัญมากกว่า Pongsak ตามหลักการของ "แถวคอยลำดับความสำคัญ (Priority queue)"

ความเร็วที่ใช้ในการทำงาน

ถึงแม้ว่าการเอาออกของข้อมูลที่สำคัญที่สุดอาจยุ่งยาก แต่ด้วยการจัดการที่เหมาะสม เราสามารถรักษาความเร็วการทำงานของแถวคอยลำดับความสำคัญไว้ที่ O (1) ได้

โครงสร้างข้อมูล

  • การใช้แถวคอยธรรมดาแต่ค้นหาตัวสำคัญที่สุด วิธีนี้จะทำให้การคืนค่ารายการใช้เวลา O (1)
  • การใช้แถวคอยตะกร้า (bucket queue) โดยการสร้างแถวคอยธรรมดาหลายๆแถว แต่ละแถวเก็บลำดับความสำคัญที่เท่าๆกัน และเรียงลำดับที่สำคัญมากสุดลงมา วิธีนี้จัดการยากพอสมควร
  • วิธีที่นิยมที่สุดคือ ฮีป (heap) เป็นการนำแนวคิดต้นไม้ในเชิงการเรียงลำดับให้ตัวที่สำคัญที่สุดอยู่บนๆ และนำตัวบนสุดมาตอบ การจัดการเช่นนี้ทำให้ การทำงานค่อนข้างจะใช้เวลาคงที่ (O (1))

ดูเพิ่ม

แถวคอยลำด, บความสำค, บทความน, ไม, การอ, างอ, งจากแหล, งท, มาใดกร, ณาช, วยปร, บปร, งบทความน, โดยเพ, มการอ, างอ, งแหล, งท, มาท, าเช, อถ, เน, อความท, ไม, แหล, งท, มาอาจถ, กค, ดค, านหร, อลบออก, เร, ยนร, าจะนำสารแม, แบบน, ออกได, อย, างไรและเม, อไร, ความสำค, ญของลำด. bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir aethwkhxyladbkhwamsakhykhwamsakhykhxngladb FIFO First In Fast Out aeteriyngtamladbkhwamsakhykarsaknkhxngsmachik xnuyatihsaknidwithikarekhathung access ENQUEUE DEQUEUE eriyngtamladbkhwamsakhy ewlathiichinkarekhathung O 1 okhrngsrangkhxmulthimirupaebbni hipinaethwkhxypkti khxmulthiekhamakxncamisiththixxkkxn First In First Out FIFO xyangirktam mibangkhrngthieratxngykihsmachikbangpraephthidthangankxnthngthimathihlng echnkarihkhiwnganthielkkwaidthakxn hrux karihsiththiphiessaekkarthanganbangpraephth echnnieracasrang aethwkhxyladbkhwamsakhy xngkvs Priority Queue epnkhiwthithungaemekhakxn aetsingthimikhwamsakhymakkwacaidxxkkxn thamikhwamsakhyethakn khxmulthiekhamakxncaidxxkkxnechnediywkbaethwkhxypktiaethwkhxyladbkhwamsakhythaiherasamarthprayuktichkhiwiddikhun enuxngcakephimkarihkhwamsakhykhxngsmachikthiaetktangkn sngphliherasamarthcderiyngaethwkhxyidihmihehmaasmkbkarthanganid eraichaethwkhxyladbkhwamsakhyinkarcdkarthangan kartrwcnb l enuxha 1 cudedn 2 brikarthimkcami 3 twxyangkarekhiynopraekrm phasa C 3 1 ladbkarephimkhxmul 3 2 phlkarthangankhxngopraekrm 4 khwamerwthiichinkarthangan 5 okhrngsrangkhxmul 6 duephimcudedn aekikhaethwkhxyladbkhwamsakhysamarthdungtwthisakhythisudldaethwxxkmakxn odyichewlakhngthi cungthaihcdkarthanganidxyangsxdkhlxngkbkhwamepncringmakyingkhun thaihsamarthcdladbinkarthanganiddi echn karcdkarthangankhxngekhruxngphimphthixnuyatihnganelkidphimphkxn ephuxcaidimesiyewlabrikarthimkcami aekikhephimraykaraenbdwyradbiwinaethwkhxy enqueue lbraykarthimikhwamsakhysungsudaelakhunkhannxxkma prioritized dequeue dungkharaykarthimikhwamsakhysungsudodyimlbraykarnnxxk peek twxyangkarekhiynopraekrm phasa C aekikh include lt bits stdc h gt using namespace std class node public int age string name node int a string b age a name b bool operator lt const node amp a const node amp b node temp1 a temp2 b if a age b age return a age gt b age else return temp1 name append temp2 name gt temp2 name append temp1 name int main priority queue lt node gt pq node b 23 Somchai node a 22 Pongsak node c 22 Manee pq push b pq push a pq push c int size pq size for int i 0 i lt size i cout lt lt pq top age lt lt lt lt pq top name lt lt n pq pop cakopraekrmkhangtn eracathakarsrang aethwkhxy odyopraekrmmienguxnikhwa ikhrthixayu Age nxythisud cathukeriykchuxkxnesmx odyhakmihlaykhnthixayuethakn khnthithukephimekhaipinkhiwphayhlngcakthukeriykkxnesmxladbkarephimkhxmul aekikh Somchai xayu 23 pi gt gt node a 23 Somchai Pongsak xayu 22 pi gt gt node b 22 Pongsak Manee xayu 22 pi gt gt node c 22 Manee phlkarthangankhxngopraekrm aekikh 22 Manee22 Pongsak23 Somchaicakphlkarthangankhxngopraekrmkhangtn casngektidwa thungaem Somchai camakxn aetwacathukeriykthaysudephraaxayumakthisud swn Manee cathukeriykepnxndbaerk thungaemwacaxayuethaknkb Pongsak aetwa Manee mathihlngsud dngnncungidkhwamsakhymakkwa Pongsak tamhlkkarkhxng aethwkhxyladbkhwamsakhy Priority queue khwamerwthiichinkarthangan aekikhthungaemwakarexaxxkkhxngkhxmulthisakhythisudxacyungyak aetdwykarcdkarthiehmaasm erasamarthrksakhwamerwkarthangankhxngaethwkhxyladbkhwamsakhyiwthi O 1 idokhrngsrangkhxmul aekikhkarichaethwkhxythrrmdaaetkhnhatwsakhythisud withinicathaihkarkhunkharaykarichewla O 1 karichaethwkhxytakra bucket queue odykarsrangaethwkhxythrrmdahlayaethw aetlaaethwekbladbkhwamsakhythiethakn aelaeriyngladbthisakhymaksudlngma withinicdkaryakphxsmkhwr withithiniymthisudkhux hip heap epnkarnaaenwkhidtniminechingkareriyngladbihtwthisakhythisudxyubn aelanatwbnsudmatxb karcdkarechnnithaih karthangankhxnkhangcaichewlakhngthi O 1 duephim aekikhaethwkhxy aethwkhxysxnghnaekhathungcak https th wikipedia org w index php title aethwkhxyladbkhwamsakhy amp oldid 7619952, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม