Stack vs Heap
Stack là một danh sách có thứ tự trong đó việc chèn và xóa các mục trong danh sách chỉ có thể được thực hiện ở một đầu được gọi là đầu. Vì lý do này, ngăn xếp được coi là cấu trúc dữ liệu Cuối cùng trong Đầu ra (LIFO). Heap là một cấu trúc dữ liệu đặc biệt dựa trên cây và nó thỏa mãn một thuộc tính đặc biệt được gọi là thuộc tính heap. Ngoài ra, một đống là một cây hoàn chỉnh, có nghĩa là không có khoảng trống giữa các lá của cây, tức là trong một cây hoàn chỉnh, mọi cấp độ đều được điền vào trước khi thêm cấp độ mới vào cây và các nút trong cấp độ nhất định được lấp đầy từ từ trái sang phải.
Ngăn xếp là gì?
Như đã đề cập trước đó, ngăn xếp là một cấu trúc dữ liệu trong đó các phần tử được thêm vào và loại bỏ chỉ từ một đầu được gọi là đỉnh. Ngăn xếp chỉ cho phép hai hoạt động cơ bản được gọi là đẩy và bật. Thao tác đẩy thêm một phần tử mới vào đầu ngăn xếp. Thao tác bật sẽ xóa một phần tử khỏi đầu ngăn xếp. Nếu ngăn xếp đã đầy, khi một thao tác đẩy được thực hiện, nó được coi là tràn ngăn xếp. Nếu một hoạt động pop được thực hiện trên một ngăn xếp đã trống, nó được coi là một quy trình dưới ngăn xếp. Do số lượng nhỏ các hoạt động có thể được thực hiện trên một ngăn xếp, nó được coi là một cấu trúc dữ liệu bị hạn chế. Ngoài ra, theo cách mà các hoạt động đẩy và bật được xác định, rõ ràng là các phần tử được thêm vào cuối cùng vào ngăn xếp sẽ đi ra khỏi ngăn xếp trước tiên. Do đó ngăn xếp được coi là cấu trúc dữ liệu LIFO.
Heap là gì?
Như đã đề cập trước đó, heap là một cây hoàn chỉnh đáp ứng thuộc tính heap. Thuộc tính Heap nói rằng, nếu y là nút con của x thì giá trị được lưu trữ trong nút x phải lớn hơn hoặc bằng giá trị được lưu trữ trong nút y (tức là giá trị (x) ≥ giá trị (y)). Thuộc tính này ngụ ý rằng nút có giá trị lớn nhất sẽ luôn được đặt ở gốc. Một heap được xây dựng bằng cách sử dụng thuộc tính này được gọi là max-heap. Có một biến thể khác của thuộc tính đống nói lên mặt trái của điều này. (tức là giá trị (x) ≤ giá trị (y)). Điều này ngụ ý rằng nút có giá trị nhỏ nhất sẽ luôn được đặt ở gốc, do đó được gọi là min-heap. Có một loạt các hoạt động được thực hiện trên heap như tìm tối thiểu (trong min-heap) hoặc tối đa (trong max-heap), xóa tối thiểu (trong min-heap) hoặc tối đa (trong max-heap), tăng (trong max -heaps) hoặc phím giảm (trong min-heaps), v.v.
Sự khác biệt giữa Stack và Heap là gì?
Sự khác biệt chính giữa ngăn xếp và heap là trong khi ngăn xếp là cấu trúc dữ liệu tuyến tính, thì heap là cấu trúc dữ liệu phi tuyến tính. Stack là một danh sách có thứ tự theo sau thuộc tính LIFO, trong khi heap là một cây hoàn chỉnh theo sau thuộc tính heap. Hơn nữa, ngăn xếp là một cấu trúc dữ liệu bị hạn chế, chỉ hỗ trợ một số hoạt động giới hạn như đẩy và bật lên, trong khi heap hỗ trợ nhiều hoạt động như tìm và xóa tối thiểu hoặc tối đa, tăng hoặc giảm khóa và hợp nhất.
