HEAP คืออะไร

HEAP SORT

   การเรียงข้อมูลโดยอาศัยโครงสร้าง Heap เป็นการเรียงข้อมูลแบบที่ดีที่สุด เพราะเป็น อัลกอริทึมที่ประกันได้ว่าเวลาที่ใช้ไม่ว่าในกรณีใดจะเป็น O(log 2 n) เสมอ 

โครงสร้าง Heap      

heap เป็นต้นไม้ไบนารีที่มีคุณสมบัติว่าโหนดใด ๆ ในต้นไม้นั้นจะมีค่าคีย์ใหญ่กว่าค่าคีย์ที่อยู่ใน left son และ right son ของมัน (ถ้าโหนดนั้นมีลูก) 

ตัวอย่างดังรูป (ก) เป็น heap ส่วนรูป (ข) ไม่ใช่ heap

รูป การเปรียบเทียบระหว่างโครงสร้าง Heap กับโครงสร้างอื่น 

                  

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

ขั้นที่ 1 สร้างโครงสร้าง heap 

ขั้นที่ 2 เอาต์พุตคีย์ที่รูตโหนด 

ขั้นที่ 3 ปรับแต่งต้นไม่ที่เหลือให้เป็น heap 

การสร้างโครงสร้าง Heap จากชุดอินพุต อาร์เรย์ใด ๆ สามารถถูกตีความเป็นต้นไม้ไบนารีได้ เช่น อาร์เรย์ที่มีค่าดังนี้ 

ความสัมพันธ์ระหว่างโครงสร้างอาร์เรย์และโครงสร้าง Heap จะมีรูปแบบเป็นต้นไม้นารีดังรูป

รูปต้นไม้ไบนารีของอาร์เรย์

การสร้าง Heap จะสร้างจากค่าอาร์เรย์ที่อ่านเข้ามาทีละค่าโดยจะสร้าง heap ขนาดที่มี I -1 โหนด เมื่อรับอีกโหนดเข้ามาก็จะได้ heap ที่มีขนาด I ทำเรื่อย ๆ จนได้ heap ขนาด n การอินพุตค่าใหม่เข้าไปใน heap ให้ถูกตำแหน่งค่าตามในต้นไม้ไบนารี หลักการมีดังนี้ (ให้ I เป็นพอยน์เตอร์ชี้ไปยังโหนด Knew) 

ขั้นที่ 1 ให้เปรียบเทียบโหนดที่เข้าใหม่กับโหนดที่เป็นพ่อ 

IF Knew > K FATHER THEN แลกที่กัน เลื่อน I ไปชี้ยังตำแหน่ง FATHER (นั่นคือ I ติดตาม Knew ขึ้นไป) 

ขั้นที่ 2 ทำขั้นที่ 1 เรื่อย ๆ จนทำไม่ได้ 

ต้นไม้ที่เห็นระหว่างการสร้าง heap นั้น เป็นการตีความข้อมูลในอาร์เรย์ ส่วนความสัมพันธ์ระหว่างพ่อ - ลูก เป็นแบบที่กล่าวมาแล้วข้างต้น หลังจากที่ข้อมูลเรียงในรูปโครงสร้าง heap แล้ว เราจะเอาเอาต์พุตค่ารูตโหนดซึ่งอยุ่ที่ตำแหน่งที่ 1 ในอาร์เรย์ การเอาต์พุตเราจะให้ค่าA(1) แลกที่กับค่าสุดท้ายของอาร์เรย์ A(8) การแทนในรูปต้นไม้ ค่าที่เอาต์พุตไปแล้วจะแทนโดยโหนดสี่เหลี่ยม ต้นไม้ที่ได้ (ไม่นับโหนดสี่เหลี่ยม) ไม่เป็นโครงสร้าง heap จากนี้ต่อไปเราต้องใช้อัลกอริทึมปรับค่าคีย์ต่าง ๆ ในต้นไม้ให้คุณสมบัติ heap การปรับต้นไม้ที่ได้จากการแลกค่าให้มีคุณสมบัติ Heap การปรับแต่งทำได้โดยเลื่อนค่าที่รูตโหนดจากบนลงมาล่าง ดังนี้ 

ขั้นที่ 1 ให้ตั้งค่าพอยน์เตอร์ I ชี้ไปยังรูตโหนด 

ขั้นที่ 2 ให้เลือกค่าที่ใหญ่ที่สุดระหว่าง left son และ right son ของโหนด I เป็นค่าที่เลื่อนมาอยู่ที่ตำแหน่ง I ส่วนค่าคีย์ที่ตำแหน่ง I ก็เลื่อนไปอยู่ที่ตำแหน่ง left son และ right son ของมันที่มีค่าใหญ่กว่า จากนั้นเลื่อนพอยน์เตอร์ I มาอยู่ที่ตำแหน่งใหม่นี้ 

ขั้นที่ 3 ทำขั้นที่ 2 จนกว่าจะทำไม่ได้ 

รูปการปรับต้นไม้ให้มีคุณสมบัติ Heap

แสดงถึงการเลื่อนค่า 22 ลงไปยังตำแหน่งถูกต้องของมัน เพื่อที่ทำต้นไม้ที่ได้เป็น heap เมื่อต้นไม้เป็นไปตามรูป (ค) ต้นไม้นั้นจะเป็น heap ซึ่งมีค่าสูงสุด 42 อยู่ที่รูตโหนด เราจะเอาต์พุต 42 ไปอยู่ที่ตำแหน่งสุดท้ายของอาร์เรย์ (ตำแหน่งก่อนค่า 90 ไป 1 ตำแหน่ง) ดังรูป (ก) ส่วนค่าที่อยู่ที่ตำแหน่งนั้น (ค่า 27) ก็ไปอยู่ที่ตำแหน่ง A(1) หรือรูตโหนด จากนั้นก็เริ่มต้นปรับแต่งต้นไม้ใหม่ให้เป็น heap ซึ่งเริ่มโดยตั้งค่า I ชี้ไปยังรูตโหน

 ประเภทของ Heap จะมีอยู่ 2 ประเภท คือ

          1. Max heap คือ ประเภทของโหนดลูกแต่ละโหนดจะเก็บข้อมูลที่มีค่าน้อยกว่าหรือเท่ากับข้อมูลใน โหนดพ่อโดยเฉพาะข้อมูลที่ตำแหน่งรูตโหนดจะมีค่ามากที่สุด

          2. Min heap คือ โหนดลูกแต่ละโหนดจะเก็บข้อมูลที่มีค่ามากกว่าหรือเท่ากับข้อมูลในโหนดพ่อแม่ โดยเฉพาะข้อมูลที่ตำแหน่งรูตโหนดจะมีค่าน้อยที่สุด

 เงื่อนไขของการแตกกิ่งก้านสาขาของโหนด คือ

          1. ทุกระดับชั้นของ heap จะแตกสาขาออกได้สองทางคือ ซ้ายและขวา การแตกโหนดจะแตกจากทางซ้ายก่อน และต้องมีโหนดในระดับรูตโหนดครบ 2 ด้านก่อนจึงจะแตกโหนดต่อไปในระดับล่างได้

          2. ค่าของโหนดที่เป็นรูตโหนดของ heap จะเป็นโหนดที่มีค่าใหญ่กว่าโหนดตัวล่าง

การเพิ่ม (Insert) โหนดเข้าไปใน Heap

          1. ถ้าโหนดที่เพิ่มเข้าไปใน heap ขณะไม่มีข้อมูลอยู่ใน heap ให้เก็บข้อมูลโหนดนั้นไว้ในตำแหน่งแรกของอาร์เรย์ที่ว่าง          

          2. ถ้าโหนดถูกเพิ่มขณะ heap มีข้อมูลหรือโหนดอยู่แล้ว การเพิ่มโหนดใหม่ใน heap  ให้ถือว่าโหนดนั้นๆเป็น Leaf  Node โดยเพิ่มโหนดในอาร์เรย์ตำแหน่งแรกที่ว่าง

           3.  ทำการเปรียบเทียบค่าโหนดใหม่กับโหนดพ่อแม่

                3.1 กรณี Max heap ถ้าโหนดใหม่ที่เพิ่มมีค่ามากกว่าโหนดพ่อ ให้สลับค่าระหว่างโหนดใหม่กับโหนดพ่อ 

3.2 กรณี Min heap ถ้าโหนดใหม่ที่เพิ่มมีค่าน้อยกว่าโหนดพ่อ ให้สลับค่าระหว่างโหนดใหม่กับโหนดพ่อ

             3.3 กรณีโหนดที่เพิ่มมีค่าน้อยกว่าโหนดพ่อแม่ใน Max heap หรือมีค่ามากกว่าโหนดพ่อแม่ Min heap ให้ถือว่าโหนดนั้นเป็น Leaf Node

          4. ทำซ้ำข้อที่ 3 จนกว่าจะถึงรูตโหนดหรือไม่มีการสลับค่าระหว่างโหนดที่เพิ่มใหม่กับโหนดพ่อ

การลบ (Delete) โหนดออกจาก heap

                การลบ (Delete) โหนดออกจาก heap ต่างจากโครงสร้างแบบต้นไม้อื่นๆ โดยสามารถลบโหนดตามต้องการแต่การลบโหนดของ heap ทำได้เฉพาะโหนดที่มีค่ามากสุดในกรณี Max heap และค่าน้อยสุดใน Min heapรายละเอียดของการลบโหนดออกจาก heap มีดังนี้

          1. ลบโหนดที่มีข้อมูลที่มีค่ามากสุดใน Max heap หรือโหนดที่มีข้อมูลที่มีค่าน้อยที่สุดใน Min heap (รูตโหนด) ผลการลบเกิดตำแหน่งว่างที่ตำแหน่งแรกในอาร์เรย์

          2. ขอยืมข้อมูลจากโหนดลูกของโหนดที่ไม่มีข้อมูล โดยนำข้อมูลที่มีค่ามากมาใส่ในโหนดพ่อ จะเกิดช่องว่างที่ตำแหน่งโหนดลูกแทน

          3. ซ้ำข้อ 2 จนโหนดลูกที่ถูกขอยืมเป็น Leaf Node

        4. ถ้า Leaf Node ที่ถูกยืมไม่เป็นโหนดสุดท้ายของ heap ให้ย้ายข้อมูลจากโหนดสุดท้ายมายังโหนดดังกล่าว

อ้างอิงข้อมูลจาก : http://bonghlub.blogspot.com/2012/09/heap-sort.html

Euclidean Algorithm

Euclidean Algorithm

ขั้นตอนวิธีของยุคลิด

ในวิชาคณิตศาสตร์ ขั้นตอนวิธีแบบยุคลิด (อังกฤษ: Euclidean Algorithm) หรือขั้นตอนวิธีของยุคลิด เป็นวิธีคำนวณตัวหารร่วมมาก (หรม.) ของจำนวนเต็มสองจำนวน ตั้งชื่อตามยุคลิด นักคณิตศาสตร์ชาวกรีกผู้อธิบายทฤษฎีนี้ในอิลิเมนต์ของยุคลิดเล่ม VII และ X 

ตัวหารร่วมมากของจำนวนเต็มสองจำนวนคือจำนวนมากที่สุดที่หารทั้งสองได้โดยไม่เหลือเศษ

รูปอย่างง่ายที่สุดของขั้นตอนวิธีแบบยุคลิดเริ่มด้วยจำนวนเต็มบวกคู่หนึ่ง และสร้างจำนวนคู่หนึ่งที่ประกอบด้วยจำนวนที่น้อยกว่าและผลต่างระหว่างจำนวนทั้งสอง กระบวนการทำซ้ำจนจำนวนทั้งสองเท่ากัน จำนวนสุดท้ายเป็นตัวหารร่วมมากของจำนวนเต็มบวกที่ขั้นตอนเริ่ม

หลักการสำคัญคือ หรม. ไม่เปลี่ยนค่าถ้านำจำนวนที่น้อยกว่าลบจำนวนที่มากกว่า เช่น หรม. ของ 252 และ 105 เท่ากับ หรม. ของ 147 

(= 252 − 105) และ 105 เพราะว่าจำนวนที่มากกว่าถูกลด การทำวิธีนี้ซ้ำทำให้ได้จำนวนเล็กลง การซ้ำนี้จึงจบอย่างแน่นอนเมื่อทั้งสองจำนวนมีค่าเท่ากัน (ถ้าทำอีกหนึ่งครั้ง จำนวนใดจำนวนหนึ่งจะเป็น 0)

หลักฐานเกี่ยวกับขั้นตอนวิธีแบบยุคลิดพบในหนังสือ Elements ของยุคลิด (ในช่วงศตวรรษที่ 3 ก่อนคริสตกาล) ทำให้เป็นขั้นตอนวิธีเก่าแก่ที่สุดเกี่ยวกับจำนวนที่ยังใช้โดยทั่วไป ขั้นตอนวิธีฉบับดังเดิมใช้สำหรับจำนวนธรรมชาติและความยาวเชิงเรขาคณิต (จำนวนจริง) แต่นักคณิตศาสตร์ได้ขยายการใช้งานไปยังจำนวนชนิดอื่น เช่น จำนวนเต็มเกาส์เซียนและพหุนามหนึ่งตัวแปร อันนำไปสู่แนวคิดเชิงพีชคณิตนามธรรมสมัยใหม่ เช่นโดเมนแบบยุคลิด ขั้นตอนวิธีของยุคลิดได้นำไปใช้กับโครงสร้างทางคณิตศาสตร์อื่นๆ เช่น เงื่อน และพหุนามหลายตัวแปร

ขั้นตอนวิธีนี้มีการประยุกต์ใช้ในทางทฤษฎีและปฏิบัติ อาจใช้ก่อกำเนิดจังหวะดนตรีที่สำคัญหลายรูปแบบที่พบในวัฒนธรรมต่างๆ ทั่วโลก ขั้นตอนวิธีนี้เป็นส่วนประกอบสำคัญของการเข้ารหัสอาร์เอสเอ (การเข้ารหัสลับแบบกุญแจอสมมาตรที่ใช้ทั่วไปในการพาณิชย์อิเล็กทรอนิกส์) ขั้นตอนวิธีนี้ใช้แก้สมการไดโอแฟนไทน์ เช่นการหาจำนวนที่สอดคล้องกับสมภาคหลายชุด(ทฤษฎีบทเศษเหลือของจีน) หรือ ตัวผกผันการคูณของเซตจำกัด และยังสามารถใช้สร้างเศษส่วนต่อเนื่องด้วยวิธีโซ่ของสเติร์มสำหรับหารากจำนวนจริงของพหุนาม และในขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มสมัยใหม่ ที่สำคัญ เป็นเครื่องมือสำหรับพิสูจน์ทฤษฎีบทในทฤษฎีจำนวนสมัยใหม่ เช่นทฤษฎีบทผลรวมกำลังสองของลากรองจ์และทฤษฎีบทมูลฐานของเลขคณิต

ถ้าปรับปรุงขั้นตอนวิธีให้ใช้เศษหารจากวิธีหารแบบยุคลิดแทนที่จะเป็นการลบ ขั้นตอนวิธีของยุคลิดคำนวณค่าตัวหารร่วมมากของจำนวนขนาดใหญ่อย่างมีประสิทธิภาพ: ขั้นตอนวิธีนี้ไม่ใช้ขั้นตอนการหารจำนวนมากกว่าห้าเท่าของจำนวนหลัก(สำหรับเลขฐานสิบ)ของจำนวนขนาดเล็กกว่า โดย Gabriel Lamé พิสูจน์เมื่อปี ค.ศ. 1844 และริเริ่มการศึกษา ทฤษฎีความซับซ้อนในการคำนวณ วิธีเพิ่มประสิทธิภาพของขั้นตอนวิธีได้พัฒนาในคริสต์ศตวรรษที่ 20

เมื่อย้อนขั้นตอนวิธีแบบยุคลิด ตัวหารร่วมมากสามารถเขียนในรูปผลรวมเชิงเส้นของสองจำนวนที่นำมาดำเนินการ แต่ละจำนวนคูณกับจำนวนเต็ม เช่น ตัวหารร่วมมากของ 252 และ 105 คือ 21 และ21 = [5 × 105] + [(−2) × 252] สมบัตินี้เรียกว่าเอกลักษณ์ของเบซู

พื้นฐาน  ตัวหารร่วมมาก

ขั้นตอนวิธีแบบยุคลิดคำนวณค่าตัวหารร่วมมาก (หรม.) ของจำนวนธรรมชาติสองจำนวน a และ b ค่าตัวหารร่วมมาก g เป็นจำนวนธรรมชาติค่ามากสุดที่หารทั้ง a และ b ลงตัว คำที่มีความหมายเหมือนกับ หรม. ได้แก่ ตัวประกอบร่วมค่ามากสุด (อังกฤษ: greatest common factor,GCF), ตัวประกอบร่วมค่ามากสุด(อังกฤษ: highest common factor,HCF) และ greatest common measure (GCM) ตัวหารร่วมมากมักเขียนแทนด้วย หรม.(a, b) หรือ (a, b) แม้ว่าสัญลักษณ์แบบหลังใช้สำหรับความคิดรวบยอดทางคณิตศาสตร์อีกหลายอย่าง เช่น เวกเตอร์พิกัดสองมิติ

ถ้า หรม.(a, b) = 1 แล้ว a กับ b เป็นจำนวนเฉพาะสัมพัทธ์ความเป็นจำนวนเฉพาะสัมพัทธ์ไม่ได้บ่งบอกว่า a หรือ b เป็นจำนวนเฉพาะเองแต่อย่างใด เช่น 6 และ 35 ต่างไม่ใช่จำนวนเฉพาะ เพราะต่างมีตัวประกอบเฉพาะจำนวนละสองตัว: 6 = 2 × 3 and 35 = 5 × 7 อย่างไรก็ตาม 6 และ 35 เป็นจำนวนเฉพาะสัมพัทธ์ ไม่มีจำนวนธรรมชาตินอกเหนือจาก 1 หารทั้ง 6 และ 35 ลงตัว เพราะไม่มีตัวประกอบเฉพาะร่วมกัน

วิธีของยุคลิดสำหรับหาตัวหารร่วมมาก (หรม.) ของความยาวเริ่มต้น BA และ DC ซึ่งต่างนิยามให้เป็นพหุคูณของความยาว"หน่วย"เดียวกัน เพราะว่า DC สั้นกว่าจึงใช้"วัด" BA แต่เพียงครั้งเดียวเพราะเศษ EA น้อยกว่า CD ใช้ EA วัดความยาว DC ที่สั้นกว่าสองครั้ง จะเหลือเศษ FC สั้นกว่า EA แล้วใช้ FC วัดความยาว EA สามครั้ง เพราะว่าขั้นตอนนี้ไม่มีเศษ จึงจบโดยมี FC เป็น หรม. ด้านขวาเป็นตัวอย่างของนิโคมาคัสโดยจำนวน 49 และ 21 ให้ผลลัพธ์ค่าตัวหารร่วมมากเป็น 7

(ประยุกต์จาก Heath 1908:300)

ตัวอย่าง การหา ห.ร.ม. โดยวิธีแบบยุคลิด

จงหา ห.ร.ม. ของ 231, 525

วิธีทำ

525 = 231*2 + 63

231 = 63*3 + 42

63 = 42*1 + 21

42 = 21*2 + 0

ห.ร.ม. ก็คือ 21

จงหา ห.ร.ม. ของ 68, 38

วิธีทำ

68 = 38*1 + 30

38 = 30*1 + 8

30 = 8*3 + 6

8 = 6*1 + 2

6 = 2*3 + 0

ห.ร.ม. ก็คือ 2

จงหา ห.ร.ม. ของ 56, 84, 140

gcd(56, 84, 140) = gcd(gcd(56, 84), 140) = gcd(56, gcd(84, 140))

วิธีทำ หา ห.ร.ม. ของ 56 กับ 84 ก่อน

84 = 56*1 + 28

56 = 28*2 + 0

ห.ร.ม. ของ 84 กับ 56 ก็คือ 28

ต่อไปหา ห.ร.ม. ของ 28 กับ 140

140 = 28*5 + 0

ห.ร.ม. ของ 140 กับ 28 ก็คือ 28

ดังนั้น ห.ร.ม. ก็คือ 28

อ้างอิงจาก : 

1. https://th.wikipedia.org/wiki/ขั้นตอนวิธีแบบยุคลิด
2. http://www.doesystem.com/f9667bfddff4bf39fa961a5a1a350014/การหา-ห.ร.ม.-กับ-อัลกอริทึมของยุคลิด.htm