การสร้าง heap จะสร้างจากค่าอาร์เรย์ที่อ่านเข้ามาทีละค่าโดยจะสร้าง heap ขนาด ที่มี I-1 โหนด เมื่อรับอีกโหนดเข้ามาก็จะได้ heap ที่มีขนาด 1 ทำเรื่ยอๆ จนได้ heap ขนาด m ดังรูปที่ 3.7
รูปที่ 7.7 การขยายโครงสร้าง heap
ในการอินพุตค่าใหม่เข้าไปใน heap ในตำเหน่งค่าตามในต้นไม้ไบนารี่ หลักการมีดังนี้ (ให้ I เป็นพอยน์เตอร์ชี้ไปยังโหนด K new )
ขั้นที่ 1 : ให้เปรียบเทียบโหนดที่เข้ามาใหม่กับโหนดที่เป็นพ่อ
IF K new Kafter THEN แลกที่กัน เลือก I ไปชี้ยังตำแหน่ง FATHER (นั่นคือ I ติดตาม K new ขึ้นไป
ขั้นที่ 2 : ทำขั้นที่ 1 เรื่อยๆ ไป จนทำไม่ได้
การปรับต้นไม้ที่ได้จากการแลกค่าให้มีคุณสมบัติ heap การปรับแต่งทำได้โดยเลื่อนค่าที่รูตโหนดจากบนลงมาล่างดังนี้
ขั้นที่ 1 : ให้ตั้งค่าพอยน์เตอร์ I ชี้ไปยังรูตโหนด
ขั้นที่ 2 : ให้เลือกค่าที่ใหญ่ที่สุดระหว่าง left son และ right son ของโหนด I เป็นค่าที่เลือนมาอยุ่ใน
ตำแหน่ง I ส่วนค่า คีย์ที่ตำเหน่ง I ก็เลื่อนพอยน์เตอร์ I มาอย่ที่ตำเหน่งใหม่นี้
ขั้นตอนที่ 3 : ทำขั้นตอนที่ 2 จนกว่าจะทำไม่ได้
รูปที่ 3.8 การปรับต้นไม้ให้มีคุณสมบัติ heap
รูปที่ 3.8 แสดงถึงการเลื่อนค่า 22 ลงไปยังตำเแหน่งที่ถูกต้องของมัน เพื่อทำต้นไม้ที่ได้เป็น heap เมื่อต้นไม้เป็นไปตามรูปที่ 7.9 (ค) ต้นไม้นั้นจะเป้น heap ซึ่งมีค่าสูงสุด 42 อยู่ที่รูตโหนด เราจะเอาต์พุต 42 ไปอยู่ที่ตำเหน่งท้ายสุดองอาร์เรย์ (ตำเหน่งก่อนค่า 90 ไป 1 ตำเหน่ง) ดังรูปที่ 3.9 (ก) ส่วนค่าที่อยู่ตำแหน่งนั้น (ค่า27) ก็ไปอยู่ที่ตำแหน่ง A(1) หรือรูตโหนด จากนั้นก็เริ่มต้นปรับแต่งต้นไม้ใหม่ให้เป็น heap ซึ่งเริ่มโดยตั้งค่า I ชี้ไปยังรูตโหนด
รูปที่ 7.9 การปรับต้นไม้ให้มีคุณสมบัติ heapที่สมบูรณ์
4 Quicjksort
quick sort เป็นอีกวิธีที่เหมาะกบลิสต์ขนาดใหญ่ และเป็นวิธีเรียงข้อมูลที่ให้ค่าเฉลี่ยของเวลาที่ใช้น้อยที่สุดเท่าที่ค้นพบวิธีหนึ่ง อย่างไรก็ดีเราต้องใช้แสตกขนาด log2n สำหรับเป็นนำแหน่งของลิสต์ย่อยที่ยังไม่ได้เรียงและเวลาที่ใช้ในกรณีเลวร้ายที่สุด จะไม่ดีกว่าแบบ O(n2)
การเรียงข้อมูลจะเริ่มโดยการใช้พอยน์เตอร์ 2 ตัวคือ F และ R ให้ F มีค่า 1 ซึ่งก็คือชี้ไปยังค่าคีย์ตัวแรกส่วน R มีค่าเท่ากับ m นั้นคือ ชี้ไปยังค่าคีย์ตัวสุดท้ายในลิสต์ การเปรียบเทียบจะกระทำระหว่าง ค่าที่ถูกชี้โดย F และ R ทุกครั้งการเปรียบเทียบจะมีการเลื่อนพอยน์เตอร์ F ไปข้างหน้า นั่นคือจากซ้ายไปขวา หรือ R จะเลื่อนถอยหลัง นั่นคือจากขวาไปซ้าย ารจะเลื่อนพอยน์เตอร์ตัวใดให้ใช้กฏต่อไปนี้ เลื่อนพอยน์เตอร์ตัวที่ไม่ใช่ชี้ไปยังค่า K 1 หรือทำหน้าที่ K 1 ในการเรียงเที่ยวนั้น เมื่อ F พบ R ที่ค่า K1 ก็เป็นอันว่าเสร็จสิ้นการเรียงเที่ยวนั้น
สมมุติให้ชุดคีย์ที่จะเรียงมีดังนี้
การเรียงแถวที่ 1
จุดนี้คีย์ 27 ได้แบ่งเป้นลิสต์ที่กำหนดให้เป็นลิสต์ย่อย 2 ลิสต์ ดังนี้
(18, 15, 22, 11) 27 (59, 37, 50, 42)
เนื่องจากมีลิสต์ย่อย (sublist) 2 ลิสต์ย่อย จึงต้องชะลอการเรียงของลิสต์ชุดหลังไว้การจะจำว่าต้องเรียงลิสต์ (59, 37, 50, 42) ภายหลังนั้นได้โดยผลัก (push) ค่า (6, 9) ซึ่งหมายถึงค่าที่ 6 ถึงค่าที่ 9 ในอาร์เรย์ A ไว้ในทุกสแตก ทุกๆ ครั้งที่มีการแตกเป็นลิสต์ย่อยๆ ให้ผลักแอดเดรสของค่าที่ยังไม่ได้เรียงไว้ในแสตก ในภายหลังเมื่อ POP แสตกจะได้ลิสต์ซึ่งต้องทำการเรียงอีก (โดยวิธีเดียวกัน)