Thuật toán sắp xếp vun đống (Heap Sort)

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về c&aacute;ch hoạt động của thuật to&aacute;n sắp xếp vun đống. Ngo&agrave;i ra, ta sẽ triển khai v&iacute; dụ về c&aacute;ch l&agrave;m việc của sắp xếp vun đống viết bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <h2 id="ftoc-heading-1" class="ftwp-heading" style="text-align: justify;">1. Kh&aacute;i niệm</h2> <p style="text-align: justify;">Sắp xếp vun đống hay Heap Sort l&agrave; một thuật to&aacute;n sắp xếp phổ biến v&agrave; hiệu quả trong lập tr&igrave;nh. Học c&aacute;ch viết thuật to&aacute;n sắp xếp vun đống đ&ograve;i hỏi kiến thức về hai loại cấu tr&uacute;c dữ liệu l&agrave; mảng v&agrave; c&acirc;y.</p> <p style="text-align: justify;">Tập hợp số ban đầu m&agrave; ch&uacute;ng ta muốn sắp xếp được lưu trữ trong một mảng, v&iacute; dụ,&nbsp;<span id="urvanov-syntax-highlighter-6107c37a85a78827556547" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-sy">[</span><span class="crayon-cn">12</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">5</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">78</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">36</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">25</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">34</span><span class="crayon-sy">]</span></span></span>&nbsp;v&agrave; sau khi sắp xếp, ch&uacute;ng ta nhận được một mảng đ&atilde; sắp xếp l&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6107c37a85a83735485264" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-sy">[</span><span class="crayon-cn">5</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">12</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">25</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">34</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">36</span><span class="crayon-sy">,</span><span class="crayon-h">&nbsp;</span><span class="crayon-cn">78</span><span class="crayon-sy">]</span></span></span></p> <p style="text-align: justify;">Sắp xếp vun đống hoạt động bằng c&aacute;ch coi c&aacute;c phần tử của mảng như một loại c&acirc;y nhị ph&acirc;n ho&agrave;n chỉnh đặc biệt được gọi l&agrave; Heap. Điều kiện ti&ecirc;n quyết l&agrave; bạn phải biết về cấu tr&uacute;c dữ liệu Heap v&agrave; c&acirc;y nhị ph&acirc;n ho&agrave;n chỉnh.</p> <h2 id="ftoc-heading-2" class="ftwp-heading" style="text-align: justify;">2. Mối quan hệ giữa chỉ số của mảng v&agrave; phần tử của c&acirc;y</h2> <p style="text-align: justify;">Một c&acirc;y nhị ph&acirc;n ho&agrave;n chỉnh c&oacute; một đặc t&iacute;nh m&agrave; ch&uacute;ng ta c&oacute; thể sử dụng để t&igrave;m n&uacute;t con v&agrave; n&uacute;t cha của bất kỳ n&uacute;t n&agrave;o.</p> <p style="text-align: justify;">Nếu chỉ số của bất kỳ phần tử n&agrave;o trong mảng l&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6107c37a85a86890375888" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">i</span></span></span>, phần tử trong chỉ số&nbsp;<span id="urvanov-syntax-highlighter-6107c37a85a88957200896" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-cn">2i</span><span class="crayon-o">+</span><span class="crayon-cn">1</span></span></span>&nbsp;sẽ trở th&agrave;nh n&uacute;t con b&ecirc;n tr&aacute;i v&agrave; phần tử trong chỉ số&nbsp;<span id="urvanov-syntax-highlighter-6107c37a85a89719361241" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-cn">2i</span><span class="crayon-o">+</span><span class="crayon-cn">2</span></span></span>&nbsp;sẽ trở th&agrave;nh n&uacute;t con b&ecirc;n phải. Ngo&agrave;i ra, n&uacute;t cha của bất kỳ phần tử n&agrave;o tại chỉ số i được cho bởi giới hạn dưới l&agrave;&nbsp;<span id="urvanov-syntax-highlighter-6107c37a85a8b953479857" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-sy">(</span><span class="crayon-v">i</span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">)</span><span class="crayon-o">/</span><span class="crayon-cn">2</span></span></span>.</p> <p><img style="width: 100%;" src="../../../public_files/30bcfd40-2fa9-4627-9a96-4fb50a776330" alt="thuat-toan-sap-xep-vun-dong" /></p> <pre class="language-cpp"><code>N&uacute;t con b&ecirc;n tr&aacute;i của 3 (Chỉ số l&agrave; 0) = Phần tử tại chỉ số (2*0+1) = Phần tử trong chỉ số 1 = 12 N&uacute;t con b&ecirc;n phải của 3 = Phần tử tại chỉ số (2*0+2) = Phần tử trong chỉ số 2 = 9 Tương tự, N&uacute;t con b&ecirc;n tr&aacute;i của 14 (Chỉ số 1) = Phần tử tại chỉ số (2*1+1) = Phần tử tại chỉ số 3 = 5 N&uacute;t con b&ecirc;n phải của 14 = Phần tử tại chỉ số (2*1+2) = Phần tử tại chỉ số 4 = 6</code></pre> <p>Ta sẽ x&aacute;c nhận rằng c&aacute;c quy tắc sẽ lu&ocirc;n đ&uacute;ng cho việc t&igrave;m kiếm n&uacute;t cha của bất kỳ n&uacute;t n&agrave;o</p> <pre class="language-cpp"><code>N&uacute;t cha của 11 (Vị tr&iacute; 2) = (2-1)/2 = 1/2 = 0.5 ~ chỉ số 0 = 3 N&uacute;t cha của 14 (Vị tr&iacute; 1) = (1-1)/2 = chỉ số 0 = 3</code></pre> <p style="text-align: justify;">Hiểu được việc &aacute;nh xạ của c&aacute;c chỉ số của mảng với c&aacute;c vị tr&iacute; trong c&acirc;y l&agrave; rất quan trọng để hiểu được c&aacute;ch thức hoạt động của cấu tr&uacute;c dữ liệu Heap v&agrave; c&aacute;ch n&oacute; được sử dụng để thực hiện sắp xếp vun đống.</p> <h2 id="ftoc-heading-3" class="ftwp-heading" style="text-align: justify;">3. Cấu tr&uacute;c dữ liệu Heap l&agrave; g&igrave;?</h2> <p style="text-align: justify;">Heap l&agrave; một cấu tr&uacute;c dữ liệu đặc biệt dựa tr&ecirc;n cấu tr&uacute;c c&acirc;y. C&acirc;y nhị ph&acirc;n được cho l&agrave; tu&acirc;n theo cấu tr&uacute;c dữ liệu đống nếu</p> <ul style="text-align: justify;"> <li>N&oacute; l&agrave; một c&acirc;y nhị ph&acirc;n ho&agrave;n chỉnh.</li> <li>Tất cả c&aacute;c n&uacute;t trong c&acirc;y tu&acirc;n theo thuộc t&iacute;nh m&agrave; ch&uacute;ng lớn hơn phần tử con của ch&uacute;ng, tức l&agrave; phần tử lớn nhất nằm ở n&uacute;t gốc v&agrave; c&aacute;c phần tử con của n&oacute; nhỏ hơn n&uacute;t gốc,&hellip;. Một Heap như vậy được gọi l&agrave; Max heap. Nếu thay v&agrave;o đ&oacute;, tất cả c&aacute;c n&uacute;t đều nhỏ hơn n&uacute;t con của ch&uacute;ng, n&oacute; được gọi l&agrave; Min Heap.</li> </ul> <p style="text-align: justify;">H&igrave;nh b&ecirc;n dưới đ&acirc;y sẽ minh họa về cấu tr&uacute;c dữ liệu Max Heap v&agrave; Min Heap.</p> <p><img style="width: 100%;" src="../../../public_files/b06e5cb8-9929-4cc8-944d-780aa35ae969" alt="thuat-toan-sap-xep-vun-dong-2" /></p> <h2 id="ftoc-heading-4" class="ftwp-heading" style="text-align: justify;">4. L&agrave;m thế n&agrave;o để để tạo một cấu tr&uacute;c Heap cho một c&acirc;y?</h2> <p style="text-align: justify;">Bắt đầu từ một c&acirc;y nhị ph&acirc;n ho&agrave;n chỉnh, ch&uacute;ng ta c&oacute; thể sửa đổi n&oacute; để trở th&agrave;nh Max Heap bằng c&aacute;ch thực hiện một h&agrave;m c&oacute; t&ecirc;n l&agrave; Heapify tr&ecirc;n tất cả c&aacute;c phần tử kh&ocirc;ng phải l&agrave; n&uacute;t l&aacute; của Heap. V&igrave; h&agrave;m Heapify sử dụng đệ quy n&ecirc;n c&oacute; thể kh&oacute; nắm bắt. V&igrave; vậy, trước ti&ecirc;n ch&uacute;ng ta h&atilde;y nghĩ về c&aacute;ch ta sẽ tạo Heap cho một c&acirc;y chỉ với ba phần tử.</p> <pre class="language-cpp"><code>heapify(array) Root = array[0] Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2]) if(Root != Largest) Swap(Root, Largest)</code></pre> <p><img style="width: 100%;" src="../../../public_files/cbd406ed-b495-4164-b073-916aeeebd815" alt="thuat-toan-sap-xep-vun-dong-3" /></p> <p><img style="width: 100%;" src="../../../public_files/aa82b31f-7d94-48b8-a877-5519a9254e61" alt="thuat-toan-sap-xep-vun-dong-4" /></p> <p style="text-align: justify;">V&iacute; dụ tr&ecirc;n đưa ra 2 trường hợp, một trong số đ&oacute; c&oacute; n&uacute;t gốc l&agrave; phần tử lớn nhất v&agrave; ch&uacute;ng ta kh&ocirc;ng cần phải l&agrave;m g&igrave; cả. V&agrave; một phần tử kh&aacute;c trong đ&oacute; n&uacute;t gốc c&oacute; một n&uacute;t con lớn hơn v&agrave; ch&uacute;ng ta cần ho&aacute;n đổi để duy tr&igrave; thuộc t&iacute;nh Max Heap.</p> <p style="text-align: justify;">Nếu ta đ&atilde; l&agrave;m việc với c&aacute;c thuật to&aacute;n đệ quy, ta c&oacute; thể đ&atilde; x&aacute;c định rằng đ&acirc;y phải l&agrave; trường hợp cơ sở (trường hợp để kết th&uacute;c lời gọi đệ quy).</p> <p style="text-align: justify;">V&iacute; dụ 2:</p> <p><img style="width: 100%;" src="../../../public_files/d546c7c5-411b-457b-87b2-a3d8588a0dcd" alt="thuat-toan-sap-xep-vun-dong-5" /></p> <p>Tuy nhi&ecirc;n, n&uacute;t tr&ecirc;n c&ugrave;ng kh&ocirc;ng phải c&oacute; cấu tr&uacute;c Max Heap nhưng tất cả c&aacute;c c&acirc;y con đều l&agrave; Max Heap.</p> <p>Để duy tr&igrave; thuộc t&iacute;nh Max Heap cho to&agrave;n bộ c&acirc;y, ch&uacute;ng ta sẽ phải tiếp tục đẩy 2 c&acirc;y xuống dưới cho đến khi n&oacute; đến đ&uacute;ng vị tr&iacute; của n&oacute;.</p> <p><img style="width: 100%;" src="../../../public_files/8ea136d0-8937-4112-ab77-d0ce9a8e8c4b" alt="thuat-toan-sap-xep-vun-dong-6" /></p> <p><img style="width: 100%;" src="../../../public_files/6edb5e21-7edc-4112-8fde-c2c887f339ca" alt="thuat-toan-sap-xep-vun-dong-7" /></p> <p style="text-align: justify;">Do đ&oacute;, để duy tr&igrave; thuộc t&iacute;nh Max Heap trong một c&acirc;y m&agrave; cả hai c&acirc;y con đều l&agrave; Max Heap, ch&uacute;ng ta cần thực hiện qu&aacute; tr&igrave;nh Heapify tr&ecirc;n n&uacute;t gốc nhiều lần cho đến khi n&oacute; lớn hơn c&acirc;y con của n&oacute; hoặc n&oacute; trở th&agrave;nh một n&uacute;t l&aacute;.</p> <p style="text-align: justify;">Ch&uacute;ng ta c&oacute; thể kết hợp cả hai điều kiện n&agrave;y trong một h&agrave;m Heapify như sau:</p> <pre class="language-cpp"><code>void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left &lt; n &amp;&amp; arr[left] &gt; arr[largest]) largest = left; if (right &lt; n &amp;&amp; arr[right] &gt; arr[largest]) largest = right; if (largest != i) { swap(&amp;arr[i], &amp;arr[largest]); heapify(arr, n, largest); } }</code></pre> <p style="text-align: justify;">H&agrave;m n&agrave;y hoạt động hiệu quả cho trường hợp cơ sở v&agrave; cho một c&acirc;y c&oacute; k&iacute;ch thước bất kỳ. Do đ&oacute;, ch&uacute;ng ta c&oacute; thể di chuyển n&uacute;t gốc đến vị tr&iacute; ch&iacute;nh x&aacute;c để duy tr&igrave; trạng th&aacute;i Max Heap cho bất kỳ k&iacute;ch thước c&acirc;y n&agrave;o miễn l&agrave; c&aacute;c c&acirc;y con c&oacute; cấu tr&uacute;c Max Heap.</p> <h2 id="ftoc-heading-5" class="ftwp-heading" style="text-align: justify;">5. X&acirc;y dựng cấu tr&uacute;c Max heap</h2> <p style="text-align: justify;">Để tạo Max Heap từ bất kỳ c&acirc;y n&agrave;o, ta c&oacute; thể bắt đầu xếp từng c&acirc;y con từ dưới l&ecirc;n v&agrave; c&oacute; được cấu tr&uacute;c Max Heap sau khi h&agrave;m được &aacute;p dụng cho tất cả c&aacute;c phần tử bao gồm cả phần tử gốc.</p> <p style="text-align: justify;">Trong trường hợp của một c&acirc;y ho&agrave;n chỉnh, chỉ số đầu ti&ecirc;n của một n&uacute;t kh&ocirc;ng phải n&uacute;t l&aacute; được cho bởi&nbsp;<span id="urvanov-syntax-highlighter-6107c37a85a97503424834" class="urvanov-syntax-highlighter-syntax urvanov-syntax-highlighter-syntax-inline crayon-theme-classic crayon-theme-classic-inline urvanov-syntax-highlighter-font-monaco"><span class="crayon-pre urvanov-syntax-highlighter-code"><span class="crayon-v">n</span><span class="crayon-o">/</span><span class="crayon-cn">2</span><span class="crayon-o">-</span><span class="crayon-cn">1</span></span></span>. Tất cả c&aacute;c n&uacute;t kh&aacute;c sau đ&oacute; l&agrave; n&uacute;t l&aacute; v&agrave; do đ&oacute; kh&ocirc;ng cần phải tạo cấu tr&uacute;c heap cho n&oacute; nữa.</p> <p style="text-align: justify;">V&igrave; vậy, ch&uacute;ng ta c&oacute; thể x&acirc;y dựng một cấu tr&uacute;c Max heap như sau:</p> <pre class="language-cpp"><code>for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(arr, n, i);</code></pre> <p><img style="width: 100%;" src="../../../public_files/eb94fbe8-c63a-4b33-8424-3938a6ef07db" alt="thuat-toan-sap-xep-vun-dong-8" /></p> <p><img style="width: 100%;" src="../../../public_files/c7bc24af-3a41-462e-bd8d-05ebe937f72b" alt="thuat-toan-sap-xep-vun-dong-9" /></p> <p><img style="width: 100%;" src="../../../public_files/6d2a16d4-396c-4036-b9e6-fac3010a3a99" alt="thuat-toan-sap-xep-vun-dong-10" /></p> <p><img style="width: 100%;" src="../../../public_files/58ed406c-d596-4d14-9bca-fd1c5aded6a7" alt="thuat-toan-sap-xep-vun-dong-11" /></p> <p><img style="width: 100%;" src="../../../public_files/5abbaf7c-08aa-4a64-91a6-952384271be6" alt="thuat-toan-sap-xep-vun-dong-12" /></p> <p style="text-align: justify;">Như thể hiện trong sơ đồ tr&ecirc;n, ch&uacute;ng ta sẽ bắt đầu bằng c&aacute;ch xếp vun đống cho c&aacute;c c&acirc;y nhỏ nhất thấp nhất v&agrave; dần dần di chuyển l&ecirc;n cho đến khi ch&uacute;ng ta đạt đến phần tử gốc.</p> <h2 id="ftoc-heading-6" class="ftwp-heading" style="text-align: justify;">6. Sắp xếp vun đống hoạt động như n&agrave;o?</h2> <ul> <li style="text-align: justify;">V&igrave; c&acirc;y thỏa m&atilde;n thuộc t&iacute;nh Max Heap, n&ecirc;n phần tử lớn nhất được lưu trữ tại n&uacute;t gốc.</li> <li style="text-align: justify;">Ho&aacute;n đổi: Loại bỏ phần tử gốc v&agrave; đặt ở cuối mảng (vị tr&iacute; thứ n). Đặt phần tử cuối c&ugrave;ng của c&acirc;y (đống) v&agrave;o chỗ trống.</li> <li style="text-align: justify;">X&oacute;a: Giảm k&iacute;ch thước của Heap đi 1 đơn vị.</li> <li style="text-align: justify;">Heapify: Tạo cấu tr&uacute;c Heap cho phần tử gốc để ch&uacute;ng ta c&oacute; phần tử cao nhất ở n&uacute;t gốc.</li> <li style="text-align: justify;">Qu&aacute; tr&igrave;nh n&agrave;y được lặp lại cho đến khi tất cả c&aacute;c phần tử của danh s&aacute;ch được sắp xếp.</li> </ul> <p><img style="width: 100%;" src="../../../public_files/c66d2fc2-6c8a-4a16-b55a-445773a095f2" alt="thuat-toan-sap-xep-vun-dong-13" /></p> <p><img style="width: 100%;" src="../../../public_files/840bd4a5-cc2e-48c9-b178-c05829062487" alt="thuat-toan-sap-xep-vun-dong-14" /></p> <p><img style="width: 100%;" src="../../../public_files/8a4d52ec-5ba9-4669-b2a8-40fa7ae04416" alt="thuat-toan-sap-xep-vun-dong-15" /></p> <p><img style="width: 100%;" src="../../../public_files/c9bec286-c423-4990-91b3-1ed4e256d54c" alt="thuat-toan-sap-xep-vun-dong-16" /></p> <p><img style="width: 100%;" src="../../../public_files/8d53245f-e344-4c92-96af-054055515ce5" alt="thuat-toan-sap-xep-vun-dong-17" /></p> <p><img style="width: 100%;" src="../../../public_files/af9f7077-470a-401b-ab69-abf7c32b4628" alt="thuat-toan-sap-xep-vun-dong-18" /></p> <p><img style="width: 100%;" src="../../../public_files/8316e2cc-e527-4353-aee9-8e5fc7037fac" alt="thuat-toan-sap-xep-vun-dong-19" /></p> <p><img style="width: 100%;" src="../../../public_files/fc1a3d39-4f4c-4a6a-93bf-d53b70abe263" alt="thuat-toan-sap-xep-vun-dong-20" /></p> <p><img style="width: 100%;" src="../../../public_files/1b96cb17-c428-4858-be2d-adf994959f46" alt="thuat-toan-sap-xep-vun-dong-21" /></p> <p><img style="width: 100%;" src="../../../public_files/a9b08d36-a76f-4756-8619-daae6a14588e" alt="thuat-toan-sap-xep-vun-dong-22" /></p> <p><img style="width: 100%;" src="../../../public_files/13bb8d8f-7261-401f-a8fb-474c3caa5038" alt="thuat-toan-sap-xep-vun-dong-23" /></p> <p><img style="width: 100%;" src="../../../public_files/670eeb5e-d220-46b6-8420-a04af757a8ba" alt="thuat-toan-sap-xep-vun-dong-24" /></p> <p><img style="width: 100%;" src="../../../public_files/2f6010b6-7e2e-4925-95a4-5498526eea9f" alt="thuat-toan-sap-xep-vun-dong-25" /></p> <p><img style="width: 100%;" src="../../../public_files/3a909b34-294d-4b2c-ad9f-26375b19b6a1" alt="thuat-toan-sap-xep-vun-dong-26" /></p> <p>Đoạn m&atilde; dưới đ&acirc;y sẽ đưa ra c&aacute;ch hoạt động.</p> <pre class="language-cpp"><code>for (int i = n - 1; i &gt;= 0; i--) { swap(&amp;arr[0], &amp;arr[i]); //Tạo cấu tr&uacute;c heap cho phần tử gốc để lấy ra phần tử lớn nhất heapify(arr, i, 0); }</code></pre> <pre class="language-cpp"><code>#include &lt;stdio.h&gt; void swap(int *a, int *b) { int c = *a; *a = *b; *b = c; } void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left &lt; n &amp;&amp; arr[left] &gt; arr[largest]) largest = left; if (right &lt; n &amp;&amp; arr[right] &gt; arr[largest]) largest = right; if (largest != i) { swap(&amp;arr[i], &amp;arr[largest]); heapify(arr, n, largest); } } void sort_heap(int arr[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(arr, n, i); for (int i = n - 1; i &gt;= 0; i--) { swap(&amp;arr[0], &amp;arr[i]); heapify(arr, i, 0); } } void print(int arr[], int n) { for (int i = 0; i &lt; n; ++i) printf("%d ", arr[i]); printf("\n"); } int main() { int arr[] = {3, 14, 11, 7, 8, 12}; int n = sizeof(arr) / sizeof(arr[0]); sort_heap(arr, n); printf("Mảng sau khi sắp xếp l&agrave;: \n"); print(arr, n); }</code></pre> <p>Kết quả:</p> <pre class="language-cpp"><code>Mảng sau khi sắp xếp l&agrave;: 3 7 8 11 12 14</code></pre> <h2 id="ftoc-heading-7" class="ftwp-heading" style="text-align: justify;">7. Độ phức tạp của thuật to&aacute;n sắp xếp vun đống</h2> <p style="text-align: justify;">Heap Sort c&oacute; độ phức tạp về thời gian l&agrave; $O(n log n)$&nbsp;cho tất cả c&aacute;c trường hợp (trường hợp tốt nhất, trường hợp trung b&igrave;nh v&agrave; trường hợp xấu nhất).</p> <p style="text-align: justify;">Chiều cao của một c&acirc;y nhị ph&acirc;n ho&agrave;n chỉnh chứa $n$ phần tử l&agrave; $log n$</p> <p style="text-align: justify;">Như ch&uacute;ng ta đ&atilde; thấy trước đ&oacute;, để tạo cấu tr&uacute;c Heap cho một phần tử c&oacute; c&aacute;c c&acirc;y con đ&atilde; l&agrave; Max Heap, ch&uacute;ng ta cần tiếp tục so s&aacute;nh phần tử với c&aacute;c phần tử con b&ecirc;n tr&aacute;i v&agrave; b&ecirc;n phải của n&oacute; v&agrave; đẩy n&oacute; xuống dưới cho đến khi n&oacute; đạt đến điểm m&agrave; cả hai c&acirc;y con của n&oacute; đều nhỏ hơn n&oacute;.</p> <p style="text-align: justify;">Trong trường hợp xấu nhất, ch&uacute;ng ta sẽ cần phải di chuyển một phần tử từ n&uacute;t gốc đến n&uacute;t l&aacute; để thực hiện nhiều ph&eacute;p so s&aacute;nh v&agrave; ho&aacute;n đổi $log(n)$.</p> <p style="text-align: justify;">Trong giai đoạn x&acirc;y dựng cấu tr&uacute;c Max Heap, ch&uacute;ng ta đ&atilde; thực hiện điều đ&oacute; cho $\frac{n}{2}$ phần tử n&ecirc;n độ phức tạp trong trường hợp xấu nhất của bước n&agrave;y l&agrave; $\frac{n}{2} \times log(n) \approx nlog(n)$.</p> <p style="text-align: justify;">Trong bước sắp xếp, ch&uacute;ng ta ho&aacute;n đổi phần tử gốc với phần tử cuối c&ugrave;ng v&agrave; tạo cấu tr&uacute;c Heap cho phần tử gốc. Đối với mỗi phần tử, điều n&agrave;y lại l&agrave;m tốn thời gian l&agrave; $log(n)$ v&igrave; ch&uacute;ng ta c&oacute; thể phải đưa phần tử đ&oacute; từ n&uacute;t gốc đến n&uacute;t l&aacute;. V&igrave; ch&uacute;ng ta lặp lại n lần n&agrave;y n&ecirc;n bước sắp xếp vun đống cũng l&agrave; $nlog(n)$.</p> <p style="text-align: justify;">Cũng v&igrave; c&aacute;c bước x&acirc;y dựng cấu tr&uacute;c Max Heap v&agrave; sắp xếp vun đống được thực hiện lần lượt n&ecirc;n độ phức tạp của thuật to&aacute;n kh&ocirc;ng được nh&acirc;n l&ecirc;n v&agrave; n&oacute; vẫn theo thứ tự $nlog(n)$.</p> <p style="text-align: justify;">Ngo&agrave;i ra, n&oacute; thực hiện sắp xếp theo độ phức tạp về kh&ocirc;ng gian l&agrave; $O(1)$. So với Sắp xếp nhanh, n&oacute; c&oacute; trường hợp xấu nhất tốt hơn l&agrave; $(O(nlogn))$. Sắp xếp nhanh c&oacute; độ phức tạp $O(n^2)$&nbsp;cho trường hợp xấu nhất. Nhưng trong c&aacute;c trường hợp kh&aacute;c, thuật to&aacute;n sắp xếp nhanh hay QuickSort sẽ nhanh hơn.</p> <h2 id="ftoc-heading-8" class="ftwp-heading" style="text-align: justify;">8. Ứng dụng của thuật to&aacute;n sắp xếp vun đống</h2> <p style="text-align: justify;">C&aacute;c hệ thống li&ecirc;n quan đến bảo mật v&agrave; c&aacute;c hệ thống nh&uacute;ng như nh&acirc;n Linux sử dụng thuật to&aacute;n sắp xếp vun đống v&igrave; giới hạn tr&ecirc;n l&agrave; $O(nlog n)$ cho thời gian chạy của HeapSort v&agrave; giới hạn tr&ecirc;n kh&ocirc;ng đổi l&agrave; $O(1)$&nbsp;cho bộ nhớ phụ của n&oacute;.</p> <p style="text-align: justify;">Mặc d&ugrave; HeapSort c&oacute; độ phức tạp về thời gian l&agrave; $O(nlogn)$&nbsp;ngay cả trong trường hợp xấu nhất, n&oacute; kh&ocirc;ng c&oacute; nhiều ứng dụng (so với c&aacute;c thuật to&aacute;n sắp xếp kh&aacute;c như QuickSort, MergeSort). Tuy nhi&ecirc;n, cấu tr&uacute;c dữ liệu cơ bản của n&oacute;, Heap, c&oacute; thể được sử dụng hiệu quả nếu ch&uacute;ng ta muốn tr&iacute;ch xuất phần nhỏ nhất (hoặc lớn nhất) từ danh s&aacute;ch c&aacute;c phần tử m&agrave; kh&ocirc;ng cần phải giữ c&aacute;c phần tử c&ograve;n lại theo thứ tự đ&atilde; sắp xếp. V&iacute; dụ như h&agrave;ng đợi ưu ti&ecirc;n.</p> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về thuật to&aacute;n sắp xếp vun đống. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n&nbsp;<a href="../../">tek4</a>&nbsp;nh&eacute;!</p>